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

10986

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

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

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.

Подписаться
Уведомить о
guest
2 комментариев
Старые
Новые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии
ренат

в решение показано. что 2^12 сравнимо с 4 mod.11 , но не сказано ничего про модуль 12