Олимпиадная задача по теории чисел: составность x²ⁿ + y²ⁿ для старших классов

  Если  x = y,  то подходит  n = 1,  ибо  x² + y²  – чётное число, большее 2. Далее мы предполагаем, что  x ≠ y.  В этом случае мы установим, что при некотором  n число  x²ⁿ + y²ⁿ  делится на 257 и не равно 257.

  Предположим, что  x²ⁿ + y²ⁿ  = 257.  Пусть   a = x^2n–1,  b = y^2n–1.  Тогда  a² + b² = 257,  и, если  a ≥ b,  то  a = 16,  b = 1  (случаи  a = 12, 13, 14, 15  легко перебираются; если же  a ≤ 11,  то   b² ≤ a² < ²⁵⁷/₂,  что невозможно). Но это противоречит условию  y > 1.

  Поскольку y не делится на простое число 257, найдётся такое натуральное q, что  x ≡ qy (mod 257).  Так как  x ≠ y  и  0 < x + y < 257,  то

q ≠ ±1 (mod 257).  Кроме того,  q ≠ 0 (mod 257).

  По малой теореме Ферма (см. задачу 160736) число  q²⁵⁶ – 1 = q²⁸ – 1 = (q – 1)(q + 1)(q² + 1)(q²² + 1)...(q²⁷ + 1) – 1  делится на 257. Первые две скобки не делятся на 257, поэтому для некоторого n ∈ {1, 2, ..., 7}  число  q²ⁿ + 1  делится на 257. Но тогда число  x²ⁿ + y²ⁿ ≡ y²ⁿ(q²ⁿ + 1) (mod 257)  также делится на 257.