Задача 111863

Темы:    [ Простые числа и их свойства ] [ Делимость чисел. Общие свойства ] [ Примеры и контрпримеры. Конструкции ] [ Основная теорема арифметики. Разложение на простые сомножители ]

Сложность: 5- Классы: 8,9,10,11

Условие

Автор: Сендеров В.А.

Дано конечное множество простых чисел P. Докажите, что найдётся такое натуральное число x , что оно представляется в виде  x = a^p + b^p  (с натуральными a, b) при всех   p ∈ P   и не представляется в таком виде для любого простого p ∉ P.

Решение

  Лемма. Пусть p – простое число. Тогда число 2ⁿ представляется в виде  a^p + b^p  тогда и только тогда, когда  n – 1  кратно p.
  Доказательство. Если  n – 1   = kp,  то  2ⁿ = (2^k)^p + (2^k)^p.
  Предположим, что  2ⁿ = a^p + b^p.  Пусть  a = 2^sk, b = 2^tm,  где k, m нечётны. Если, скажем,  s > t,  то  a^p + b^p = 2^pt(2^p(s–t)k^p + m^p),  и число 2ⁿ имеет нечётный делитель  2^p(s–t)k^p + m^p,  больший единицы, что невозможно. Значит,  s = t,  и тогда  a^p + b^p = 2^pt(k^p + m^p).  Если  p = 2,  то число  k^p + m^p  имеет остаток 2 при делении на 4, и если оно больше 2, то 2ⁿ имеет нечётный делитель  ½ (k^p + m^p),  больший 1, что невозможно. Поэтому
k = m = 1,  2ⁿ = 2·2^pt,  и  n = pt + 1,  что и требовалось.
  Если же  p > 2,  то оно нечётно, и  k^p + m^p = (k + m)(k^p–1 – k^p–2m + ... + m^p–1).   Вторая скобка нечётна и является делителем числа 2ⁿ, поэтому она равна 1; значит,  k^p + m^p = k + m,  что возможно лишь при  k = m = 1,  и тогда опять получаем  n = pt + 1.
  Пусть  P = {p₁, ..., p_n}.  Положим  x = 2^{p₁p₂...p_n+1}.  Тогда по лемме это число удовлетворяет условию задачи.

Замечания

Легко видеть, что существует бесконечно много таких чисел; подходят, например, все числа вида  

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

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