Задача 78591

Темы:    [ Арифметическая прогрессия ] [ Арифметика остатков (прочее) ] [ Периодичность и непериодичность ] [ Китайская теорема об остатках ]

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

Условие

Доказать, что те натуральные K, для которых  K^K + 1  делится на 30, образуют арифметическую прогрессию. Найти её.

Решение

В решении задачи 78581 показано, что последние цифры чисел nⁿ (n натуральное) образуют периодическую последовательность с периодом 1, 4, 7, 6, 5, 6, 3, 6, 9, 0, 1, 6, 3, 6, 5, 6, 7, 4, 9, 0. Поэтому  K^K + 1  оканчивается нулём в точности при  K = 10m + 9,  m – неотрицательное целое. Остается выяснить, при каких m это число делится на 3. Пусть  m = 3n + r,  0 ≤ r < 3.  Тогда  K^K + 1 ≡ r + 1  (mod 3),  значит, должно быть  r = 2.  Отсюда получаем ответ.

Ответ

Прогрессия  k = 30n – 1,  где n – натуральное число.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	29
Год	1966
вариант
	1
Класс	9,10,11
Тур	1
задача
Номер	4