Малая теорема Ферма

В данной публикации мы рассмотрим одну из главных теорем в теории целых чисел –  малую теорему Ферма, названную так в честь французского математика Пьера де Ферма. Также разберем пример решения задачи для закрепления представленного материала.

Формулировка теоремы

1. Исходная

Если p – это простое число, a – целое число, не делящееся на p, то a^p-1 – 1 делится на p.

Формально пишется так: a^p-1 ≡ 1 (mod p).

Примечание: простым называется натуральное число, которое делится без остатка только на единицу и само себя.

Например:

• a = 2
• p = 5
• a^p-1 – 1 = 2^5-1 – 1 = 2⁴ – 1 = 16 – 1 = 15
• число 15 делится на 5 без остатка.

2. Альтернативная

Если p является простым числом, a – любым целым числом, то a^p сравнимо с a по модулю p.

a^p ≡ a (mod p)

История нахождения доказательства

Пьер де Ферма сформулировал теорему в 1640 году, однако сам ее не доказал. Позднее это сделал Готфрид Вильгельм Лейбниц – немецкий философ, логик, математик и т.д. Считается, что доказательство у него было уже к 1683 году, правда, оно так и не было опубликовано. Примечательно то, что Лейбниц открыл теорему сам, не зная о том, что она уже ранее была сформулирована.

Впервые доказательство теоремы было опубликовано в 1736 году, и принадлежит оно швейцарскому, немецкому и российскому математику и механику, Леонарду Эйлеру. Малая теорема Ферма является частным случаем теоремы Эйлера.

Пример задачи

Найдите остаток от деления числа 2¹² на 12.

Решение

Давайте представим число 2¹² как 2 ⋅ 2¹¹.
11 – это простое число, следовательно, по малой теореме Ферма получаем:
2¹¹ ≡ 2 (mod 11).
Значит, 2 ⋅ 2¹¹ ≡ 4 (mod 11).
Таким образом, число 2¹² делится на 12 с остатком, равным 4.