ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116652
Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ]
[ Принцип крайнего (прочее) ]
[ Доказательство от противного ]
[ Примеры и контрпримеры. Конструкции ]
[ Уравнения в целых числах ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

Для натурального a обозначим через P(a) наибольший простой делитель числа  a² + 1.
Докажите, что существует бесконечно много таких троек различных натуральных чисел a, b, c, что  P(a) = P(b) = P(c).


Решение

  Пусть p – нечётное простое число, а  a < p  – такое натуральное число, что  a² + 1  кратно p; тогда числа a и  p – a  различны, и  P(a) = P(p – a) = p.  Действительно, числа  a² + 1  и  (p – a)² + 1 = (a² + 1) + p(p – 2a)  делятся на p и меньше p²; значит, они не могут делиться на простые числа, большие p.  Дальше можно рассуждать по-разному.

  Первый способ. Предположим противное. Тогда существует лишь конечное число простых чисел p, для которых уравнение  P(x) = p  имеет хотя бы три натуральных решения. Обозначим через s максимальное такое простое число (если таких простых не существует, положим  s = 2),  а через S – произведение всех простых чисел, не превосходящих s.
  Пусть  p = P(S);  тогда p взаимно просто с S и потому  p > s.  Пусть a – остаток от деления S на p; тогда  a² + 1  кратно p, значит,  P(a) = P(p – a) = p.  Одно из чисел a и  p – a  чётно; обозначим его через b.
  Число  (b + p)² + 1  делится на 2p (b чётно, а p – нет), поэтому  q = P(b + p) ≥ p.
  Если  q = p,  то уравнение  P(x) = p  имеет три решения – b,  p – b,  p + b;  а это невозможно по предположению.
  Если  q > p,  число  (b + p)² + 1 делится на 2pq. Это означает, что  q < b + p  (в противном случае  (b + p)² + 1 ≤ (2p – 1)q + 1 < 2pq).  Обозначая через c остаток от деления числа  b + p  на q, получаем  P(c) = P(q – c) = P(b + p) = q > p > s,  что противоречит выбору s.

  Второй способ. Мы будем использовать тождество   (m² + 1)((m – 1)² + 1) = (m² – m + 1)² + 1,   (*).
Из него следует, что  P(m² – m + 1) = max (P(m), P(m – 1)).
  Предположим противное. Пусть N – наибольшее число, встречающееся в описанных тройках; если таких троек нет, положим  N = 3.  Последовательность натуральных чисел  P(N + 1), P(N + 2), ...  не может строго убывать. Значит, найдётся такое число  n > N + 1,  что  P(n – 1) ≤ P(n).  Тогда  P(n² – n + 1) = max (P(n), P(n – 1)) = P(n).  Из чисел  P(n), P(n + 1), ..., P(n² – n)  выберем максимальное – P(m). Имеем
P(m² – m + 1) = max (P(m),  P(m – 1)) = P(m)  и  P(m² + m + 1) = max (P(m),  P(m + 1)) = P(m).
  Таким образом, тройка  m,  m² – m + 1,  m² + m + 1  удовлетворяет условию, и  m > N. Противоречие.

  Третий способ. Для каждого натурального  n ≥ 1  рассмотрим число   ;   оно имеет вид    при некоторых натуральных an, bn  (ясно, что  an < an+1).
  Тогда  ,  откуда     Значит,   ;   ясно, что  bn < an  и
an ≥ 22n+1 ≥ 8,  поэтому все простые делители числа    не превосходят  max (5, bn) < an.
  Итак,  pn = P(an) < an.  С другой стороны,    кратно 5, значит,  pn ≥ 5.  Обозначим через cn остаток от деления an на pn. Тогда числа cn,  pn – cn  различны и  P(cn) = P(pncn) = P(an).  Мы предъявили бесконечно много различных троек требуемого вида.

Замечания

Идея последнего способа решения связана с теорией уравнений Пелля. См. книгу В.О. Бугаенко "Уравнения Пелля".

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2010-2011
Этап
Вариант 5
класс
Класс 11
Задача
Номер 11.7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .