В данной публикации мы рассмотрим одну из главных теорем в теории целых чисел – малую теорему Ферма, названную так в честь французского математика Пьера де Ферма. Также разберем пример решения задачи для закрепления представленного материала.
Формулировка теоремы
1. Исходная
Если p – это простое число, a – целое число, не делящееся на p, то ap-1 – 1 делится на p.
Формально пишется так: ap-1 ≡ 1 (mod p).
Примечание: простым называется натуральное число, которое делится без остатка только на единицу и само себя.
Например:
- a = 2
- p = 5
- ap-1 – 1 = 25-1 – 1 = 24 – 1 = 16 – 1 = 15
- число 15 делится на 5 без остатка.
2. Альтернативная
Если p является простым числом, a – любым целым числом, то ap сравнимо с a по модулю p.
ap ≡ a (mod p)
История нахождения доказательства
Пьер де Ферма сформулировал теорему в 1640 году, однако сам ее не доказал. Позднее это сделал Готфрид Вильгельм Лейбниц – немецкий философ, логик, математик и т.д. Считается, что доказательство у него было уже к 1683 году, правда, оно так и не было опубликовано. Примечательно то, что Лейбниц открыл теорему сам, не зная о том, что она уже ранее была сформулирована.
Впервые доказательство теоремы было опубликовано в 1736 году, и принадлежит оно швейцарскому, немецкому и российскому математику и механику, Леонарду Эйлеру. Малая теорема Ферма является частным случаем теоремы Эйлера.
Пример задачи
Найдите остаток от деления числа 212 на 12.
Решение
Давайте представим число 212 как 2 ⋅ 211.
11 – это простое число, следовательно, по малой теореме Ферма получаем:
211 ≡ 2 (mod 11).
Значит, 2 ⋅ 211 ≡ 4 (mod 11).
Таким образом, число 212 делится на 12 с остатком, равным 4.
