Олимпиадная задача по теории чисел: делимость и принцип крайнего, сложность 4, 8-10 класс

  Пусть p – наименьший простой делитель числа n. Представим n в виде p^mk, где k не делится на p. По условию число  p + k – 1  является делителем n.

  Если  (p + k – 1, k) > 1,  то  (p – 1, k) = (l, k) > 1.  Таким образом, число k имеет какой-то делитель d,  2 ≤ d ≤ p – 1.  Противоречие с выбором числа p. Следовательно,  p + k – 1 = p^α.

  Пусть  α ≥ 2.  Тогда p² и k – взаимно простые делители числа n, то есть  p² + k – 1  – делитель числа n. При этом  p² + k – 1  взаимно просто с k, поскольку в противном случае k имеет общий делитель с  p² – 1 = 2(p – 1)· ½(p + 1),  что снова противоречит выбору числа p. Значит,  p² + k – 1 = p^β,  где  β ≥ 3.  Но тогда  p^β = p² + k – 1 = p² + (p + k – 1) – p = p(p + p^α–1 – 1),  что не делится на p². Противоречие.

  Следовательно,  k = 1,  то есть  n = p^m.  Нетрудно убедиться, что все такие числа удовлетворяют условию.

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