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

Проект МЦНМО
при участии
школы 57
Задача 73597
Темы:    [ Деление с остатком ]
[ Принцип Дирихле (прочее) ]
[ Теорема Эйлера ]
[ НОД и НОК. Взаимная простота ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

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

Замечания

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

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

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

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

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

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