ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66080
Тема:    [ Арифметика остатков (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

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


Ответ

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

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

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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .