Задача 110120

Темы:    [ Простые числа и их свойства ] [ Уравнения в целых числах ] [ Разложение на множители ]

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

Условие

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

Найдите все простые p, для каждого из которых существуют такие натуральные x и y, что  p^x = y³ + 1.

Решение

  y³ + 1 = (y + 1)(y² – y + 1),  поэтому  y + 1 = p^α,  y² – y + 1 = p^β,  где  α > 0,  β ≥ 0.

  Первый способ. Если  β = 0,  то  y = 1,  p = 2  (x = 1).
  Пусть  β > 0.  Тогда p – общий делитель чисел  y + 1  и  y² – y + 1,  а значит, и чисел  y + 1  и  (y + 1)² – (y² – y + 1) = 3y.
  Поскольку  НОД(y, y + 1) = 1,  p = 3.  Так бывает:  3² = 2³ + 1.

  Второй способ.  p^x = (p^α – 1)³ + 1 = p^α(3 + A),  где A делится на p.
  Поскольку  3 + A = p^γ  (γ ≥ 0),  то либо p = 3,  либо  γ = 0.  В последнем случае  p^x = p,  x = 1.  Значит,  y = y³,  откуда  y = 1,  p = 2.

Замечания

Второй способ фактически доказывает следующее
Утверждение. Если  p^x = y²ⁿ⁺¹ + 1  (x, y, n – натуральные) и  y > 1,  то  2n + 1 = p^z,  где z – натуральное число.

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

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