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

Проект МЦНМО
при участии
школы 57
Задача 115411
Темы:    [ Малая теорема Ферма ]
[ Арифметика остатков (прочее) ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Даны натуральные числа x и y из отрезка  [2, 100].  Докажите, что при некотором натуральном n число x2n + y2n  – составное.


Решение

  Если  x = y,  то подходит  n = 1,  ибо  x² + y²  – чётное число, большее 2. Далее мы предполагаем, что  xy.  В этом случае мы установим, что при некотором  n число  x2n + y2n  делится на 257 и не равно 257.
  Предположим, что  x2n + y2n  = 257.  Пусть   a = x2n–1b = y2n–1.  Тогда  a² + b² = 257,  и, если  a ≥ b,  то  a = 16,  b = 1  (случаи  a = 12, 13, 14, 15  легко перебираются; если же  a ≤ 11,  то   b2a2 < 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 + y2ny2n(q2n + 1) (mod 257)  также делится на 257.

Замечания

Известно, что для простого  p = 4k + 1  существует ровно одна такая пара натуральных чисел  a > b,  что  a² + b² = p.  Это позволяет избежать перебора в середине решения.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2008-2009
Этап
Вариант 5
Класс
Класс 11
задача
Номер 06.4.11.8
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2008-2009
Этап
Вариант 5
Класс
Класс 10
задача
Номер 06.4.10.8

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

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