Условие
Для натурального 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(pn – cn) = P(an). Мы предъявили бесконечно много различных троек требуемого вида.
Замечания
Идея последнего способа решения связана с теорией уравнений Пелля. См. книгу В.О. Бугаенко "Уравнения Пелля".
Источники и прецеденты использования
|
олимпиада |
Название |
Всероссийская олимпиада по математике |
год |
Год |
2010-2011 |
Этап |
Вариант |
5 |
класс |
Класс |
11 |
Задача |
Номер |
11.7 |