Олимпиадная задача по теории чисел: делимость и принцип крайнего. Классы 8–10

  Легко проверить, что числа вида p^k, где p – простое, а также число 12 удовлетворяют условию задачи. Покажем, что других чисел, удовлетворяющих условию, не существует.

  Случай нечётного n рассмотрен в 209752. Пусть n чётно и не является степенью двойки; представим его в виде  n = 2^mk,  где  m ≥ 1,  а  k > 1  – нечётно.

  Заметим, что  k + 2 – 1 = k + 1  – делитель n.   Поскольку  (k + 1, k) = 1,   k + 1 = 2^α,  α > 1.

  Поэтому  2² + k – 1 = k + 3  – тоже делитель n. Заметим, что  k + 3 = (k + 1) + 2 = 2^α + 2  не делится на 4. Кроме того,  (k + 3, k) = (3, k) ≤ 3.

  Из этого следует, что  k + 3 ≤ 2·3 = 6,  и k ≤ 3.

  Значит,  n = 2^m·3.  Но  m = 1  не подходит;  m ≥ 3  также не подходит, так как в этом случае мы получили бы, что  2³ + 3 – 1 = 10  – также делитель n.

n – степень простого числа или  n = 12.