Задача 73597

Темы:    [ Деление с остатком ] [ Принцип Дирихле (прочее) ] [ Теорема Эйлера ] [ НОД и НОК. Взаимная простота ]

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

Условие

Докажите, что для любого нечётного натурального числа a существует такое натуральное число b, что  2^b – 1  делится на a.

Решение

Рассмотрим числа  2⁰ – 1,  2¹ – 1,  ...,  2^a – 1.  Этих чисел  a + 1.  Какие-то два из них дают одинаковые остатки при делении на a, потому что различных таких остатков существует всего a. Пусть, скажем, числа  2^k – 1  и  2^m – 1  дают одинаковые остатки при делении на a и  k < m.  Тогда число  (2^m – 1) – (2^k – 1) = 2^k(2^m–k – 1)  делится на a и, поскольку a нечётно,  2^m–k – 1  делится на a.

Замечания

1. Точно так же доказывается и более общий факт: если натуральные числа a и c взаимно просты, то найдётся такое натуральное b, что  c^b – 1  делится на a.

2. Утверждение задачи вытекает и из теоремы Эйлера.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	4
Название	Теоремы Ферма и Эйлера
Тема	Малая теорема Ферма
задача
Номер	04.158
журнал
Название	"Квант"
год
Год	1971
выпуск
Номер	1
Задача
Номер	М62