Задача 66080

Тема:    [ Арифметика остатков (прочее) ]

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

Условие

Автор: Меньщиков А.Б.

Найдите все такие пары натуральных чисел a и k, что для всякого натурального n, взаимно простого c a, число  a^kn+1 – 1  делится на n.

Решение

  Если  a = 1,  то  a^kn+1 – 1 = 0,  а значит, делится на n.
  Пусть  a ≥ 2.  Возьмём  n = a^k – 1,  тогда  a^k ≡ 1 (mod n),  и следовательно,  0 ≡a^kn+1 – 1 ≡ (a^k)^kn–1·a – 1 ≡ a – 1 (mod a^k – 1).
  Такое может быть только при  k = 1,  но в этом случае  a^kn+1 – 1 = a² – 1  должно делиться на все n, что невозможно. Таким образом, пары, в которых  a ≥ 2,  нам не подходят.

Ответ

a = 1,  k – любое натуральное число.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	80
Год	2017
класс
Класс	9
задача
Номер	4