- Теорема Вильсона
-
Теорема Вильсона — теорема теории чисел, которая утверждает, что
Натуральное число является простым тогда и только тогда, когда делится на p.
Практическое использование теоремы Вильсона для определения простоты числа нецелесообразно из-за сложности вычисления факториала.
Содержание
Доказательство
ДоказательствоНеобходимость
Пусть p - простое.
- Способ 1.
Рассмотрим . Множество ненулевых классов классов вычетов по простому модулю p по умножению является группой, и тогда - это произведение всех элементов группы . Поскольку - группа, то для каждого ее элемента существует единственный обратный элемент . Соответствие разбивает группу на классы: если (что равносильно , то есть , поскольку у уравнения второй степени может быть не более двух решений), то класс содержит один элемент , в противном случае класс состоит из двух элементов - . Значит, если класс содержит один элемент , то произведение всех его элементов равно , а если класс содержит 2 элемента, то произведение всех его элементов равно 1. Теперь в произведении сгруппируем элементы по классам, все произведения по 2-хэлементным классам просто равны 1:
- Способ 2.
Группа циклична, т.е. существует элемент такой, что для всякого элемента существует такое, что . Поскольку имеет элемент, то пробегает значения от 0 до , когда пробегает всю группу вычетов. Тогда
- Способ 3.
- поле, поэтому в нем имеет место теорема Безу, т.е. многочлен степени имеет не более корней. Рассмотрим многочлены и . Оба многочлена имеют корни (для это получается по малой теореме Ферма), степени многочленов равны , старшие коэффициенты одинаковы. Тогда многочлен имеет как минимум те же корней, но его степень не более . Значит по теореме Безу тождественно равен нулю, т.е. для всех будет , в частности , что равносильно . Получаем утверждение теоремы для , т.к. четно и значит .■
Достаточность
Если составное и , то , а при получаем .
Обобщение
Как было впервые доказано Гауссом, при любом для произведения всех натуральных чисел, не превосходящих n и взаимно-простых с n, имеет место сравнение:
где — нечётное простое число, — натуральный показатель.
История
Теорема впервые была сформулирована Уорингом в 1770 году и принадлежала, по его словам, Вильсону (англ.). Доказал её Лагранж в 1771 году.
См. также
Литература
- Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
- Трост Э. Простые числа, пер. с нем., М., 1959
- Виноградов И. М. Основы теории чисел. — 5 изд.. — М.-Л.: Гостехиздат, 1952.
Категории:- Тесты простоты
- Теория чисел
Wikimedia Foundation. 2010.