Теорема Ферма
Над её доказательством около 350 лет работало много ученых. И в 1994 году она была полностью доказана Эндрю Уайлсом.
Два целых числа и называются сравнимы по модулю натурального числа , если при делении на они дают одинаковые остатки; или если их разность делится на . Записывается это следующим образом
Примеры решения задач
Задание | Записать и проверить малую теорему Ферма для и . |
Решение | По малой теореме Ферма делится на . Подставляя заданные значения и , получим:
Действительно, Для заданных значений теорема верна. |
Задание | Найти остаток от деления на 101. |
Решение | Число 101 является простым числом. Согласно малой теореме Ферма имеет место следующее сравнение:
Домножим правую и левую часть этого сравнения на 9, получим:
|
Ответ | Остаток от деления на 101 равен 9 |
Задание | Доказать, что делится на 143. |
Решение | Разложим 143 на простые множители:
Покажем, что делится на 11 и на 13. Действительно, по теореме Ферма и . По свойству сравнений, если , то для любого натурального , справедливо . Тогда последние два сравнения можно переписать в виде и . Таким образом, делится на 11 и на 13, а, следовательно, делится и на 143. Что и требовалось доказать. |