|
|
 |
Условие
Даны натуральные числа x и y из отрезка [2, 100]. Докажите, что при некотором натуральном n число x2n + y2n – составное.
Решение
Если x = y, то подходит n = 1, ибо x² + y² – чётное число, большее 2. Далее мы предполагаем, что x ≠ y. В этом случае мы установим, что при некотором n число x2n + y2n делится на 257 и не равно 257.
Предположим, что x2n + y2n = 257. Пусть a = x2n–1, b = y2n–1. Тогда a² + b² = 257, и, если a ≥ b, то a = 16, b = 1 (случаи a = 12, 13, 14, 15 легко перебираются; если же a ≤ 11, то b2 ≤ a2 < 257/2, что невозможно). Но это противоречит условию y > 1.
Поскольку y не делится на простое число 257, найдётся такое натуральное q, что x ≡ qy (mod 257). Так как x ≠ y и 0 < x + y < 257, то
q ≠ ±1 (mod 257). Кроме того, q ≠ 0 (mod 257).
По малой теореме Ферма (см. задачу 60736) число q256 – 1 = q28 – 1 = (q – 1)(q + 1)(q² + 1)(q22 + 1)...(q27 + 1) – 1 делится на 257. Первые две скобки не делятся на 257, поэтому для некоторого n ∈ {1, 2, ..., 7} число q2n + 1 делится на 257. Но тогда число x2n + y2n ≡ y2n(q2n + 1) (mod 257) также делится на 257.
Замечания
Известно, что для простого p = 4k + 1 существует ровно одна такая пара натуральных чисел a > b, что a² + b² = p. Это позволяет избежать перебора в середине решения.
