Ма́лая теоре́ма Ферма́ - классическая теорема теории чисел, которая утверждает, что
Если p - простое число, и не делится на
, то
Другими словами,
при делении нацело на
даёт в остатке 1.
Равносильная формулировка:
Для любого простого и целого
:
делится на
Теорема называется малой во избежание путаницы с Великой теоремой Ферма.
Доказательство
Докажем, что для любого простого p и целого неотрицательного a, делится на p. Доказываем индукцией по a.
База. Для a=0, и делится на p.
Переход. Пусть утверждение верно для a=k. Докажем его для a=k+1.
Но делится на p по предположению индукции. Что же касается остальных слагаемых, то
. Для
, числитель этой дроби делится на p, а знаменатель - взаимно прост с p, следовательно,
делится на
. Таким образом, вся сумма
делится на p.
Для отрицательных a и нечётных p теорему легко доказать подстановкой b=-a. Для отрицательных a и p=2 истинность теоремы следует из ■
Свойства и некоторые следствия
Если - простое число, а
и
- такие положительные целые числа, что
, тогда
. Это утверждение используется в системе шифрования с открытым ключом RSA.
Если - простое число, отличное от 2 и 5, то число
, запись которого состоит из одних девяток, делится на
. Отсюда легко следует, что для любого целого числа
, которое не делится на 2 и на 5, можно подобрать число, состоящее только из девяток, которое делится на
[1]. Этот факт используется в теории признаков делимости и периодических дробей.
Обобщения
Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теорем Кармайкла и Лагранжа для конечных циклических групп.
Малая теорема Ферма также имеет изящное обобщение в теории конечных полей.
Псевдопростые числа
Основная статья: Псевдопростое число
Обращение малой теоремы Ферма неверно, то есть приведенные в определении формулы могут выполняться не только для простых чисел: если и
- взаимно простые числа такие, что
делится на p, то число
может не быть простым. В случае, когда
является составным, это число называется псевдопростым по основанию a.
Пример: Ф. Саррус в 1820 году нашёл, что число делится на 341 (потому что N делится на
). Но 341 - составное число:
- это первое псевдопростое число по основанию 2.
Число p, являющееся псевдопростым по основанию a для всех a, взаимно простых с p, называется числом Кармайкла (например, 561 - наименьшее из чисел Кармайкла).
Хотя выполнение теоремы Ферма не гарантирует, что p - простое число, теорема может быть полезна для тестирования числа: если не делится на
, то p - составное число.
История
Пьер Ферма сформулировал исходное утверждение теоремы около 1636 года. Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю (Bernard Frénicle de Bessy) содержало следующее положение: p делит в случае, когда p является простым числом и a не делится на p. Опубликовано в посмертном издании его трудов (1660).
Ещё в древности китайским математикам была известна гипотеза (иногда называемая «Китайской гипотезой»), что p является простым числом в том и только в том случае, когда (фактически, частный случай малой теоремы Ферма)[2]. Тем не менее, обратное утверждение (о том, что из
следует, что p простое), а, следовательно, и гипотеза в целом, оказались неверными (см. выше).
Существует также предположение, что китайская гипотеза была выдвинута примерно за 2000 лет до аналогичных работ Ферма. Стоит отметить, что гипотеза могла быть известна и другим математикам древности, даже несмотря на то, что она оказалась частично неверной. Тем не менее, в некоторых источниках[3] утверждается, что предположение относительно столь раннего появления гипотезы является распространённым заблуждением, а в действительности гипотеза была выдвинута лишь в 1872 году.
Сам Ферма оставил свою теорему без доказательства. Первым, кому удалось его найти, был Готфрид Вильгельм Лейбниц, в рукописях которого утверждается, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо[1]. Но работа Лейбница не была опубликована, и доказательство (очень похожее) в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.
Доказательство малой теоремы Ферма, основанное на том, что целые числа сравнимы в некотором порядке с числами
, было опубликовано в 1806 году Джеймсом Айвори.
Список литературы
Винберг Э. Б. Малая теорема Ферма и ее обобщения // Математическое просвещение. - 2008. - В. 12. - С. 43-53.
Гиндикин С. Г. Малая теорема Ферма // Квант. - 1972. - № 10.
Данциг, Т. Числа - язык науки. - М.: Техносфера, 2008. - С. 111. - ISBN 978-5-94836-172-7
Для подготовки данной работы были использованы материалы с сайта http://ru.wikipedia.org/
Дата добавления: 27.01.2013