Назад
Задача

Саша выбрал натуральное число  N > 1  и выписал в строчку в порядке возрастания все его натуральные делители:  d1 < ... < ds  (так что  d1 = 1  и

ds = N).  Затем для каждой пары стоящих рядом чисел он вычислил их наибольший общий делитель; сумма полученных  s – 1  чисел оказалась равной

N – 2.  Какие значения могло принимать N?

Решение

  Заметим, что  ds+1–i = N/di  при всех  i = 1, 2, 3, ..., s.

  Число  di+1di  делится на  (di, di+1),  так что  (di, di+1) ≤ di+1di.  При  i = 1, 2, s – 1  обозначим  ri = (di+1di) – (di, di+1) ≥ 0.  По условию

(d2d1) + (d3d2) + ... + (ds – ds–1) = ds – d1 = N – 1,  а  (d1, d2) + (d2, d3) + ... + (ds–1, ds) = N – 2.

  Вычитая, получим  r1 + r2 + ... + rs–1 = 1.  Это означает, что  rk = 1  для некоторого k, а все остальные ri равны нулю.

  Левая часть равенства  (dk+1dk) – (dk, dk+1) = 1  делится на  (dk, dk+1),  поэтому  (dk, dk+1) = 1  и  dk+1dk = 2.  Это возможно, только если каждое из чисел dk и dk+1 нечётно.

  Так как dk и dk+1 – два последовательных делителя числа N, то N/dk+1 и N/dk – тоже два последовательных делителя числа N: если  N/dk+1 = dm,  то

N/dk = dm+1.  При этом  (dm, dm+1) = N/[dk,dk+1] = N(dk,dk+1)/dkdk+1 < N(dk+1dk)/dkdk+1 = dm+1dm.

  Значит,  rm > 0,  что возможно лишь при  k = m  (и, следовательно,  s = 2k).

  Итак,  dk+1 = N/dk,  то есть число  N = dkdk+1  нечётно. Но тогда  ds–1N/3,  откуда  (ds–1, ds) ≤ ds–1N/3.  Следовательно,  1 ≥ rs–12N/3N/3 = N/3,  то есть  N ≤ 3.  Поскольку  N > 1,  получаем единственно возможное значение  N = 3,  которое, как легко убедиться, удовлетворяет условию.

Ответ

N = 3.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет