Теорема Вильсона - фундаментальное утверждение теории чисел, имеющее как теоретическое, так и практическое значение. Давайте разберемся в ее сути, истории открытия и возможностях использования.
Суть теоремы Вильсона
Теорема Вильсона формулируется следующим образом: для любого простого числа p выполняется равенство
(p - 1)! + 1 ≡ 0 (mod p)
Где ! - оператор факториала, а ≡ означает равенство чисел по модулю p. Иными словами, сумма факториала от p-1 и единицы делится нацело на простое число p.
Для примера рассмотрим простое число p = 5. Тогда (p - 1)! = 4! = 1·2·3·4 = 24. Прибавим 1 и получим 25. Действительно, 25 делится нацело на 5.
Интуитивное понимание
Интуитивно теорема Вильсона может быть понята следующим образом. Факториал (p-1)! содержит произведение всех целых чисел от 1 до p-1. Если какое-либо из этих чисел имело общий делитель с p, помимо 1, то p не было бы простым. Поэтому домножение этого произведения на любое целое число и сложение 1 приводит к числу, обязательно делящемуся на p.
Связь с другими утверждениями теории чисел
Теорема Вильсона тесно связана с Малой теоремой Ферма, которая утверждает, что если p - простое число, а a - целое число, взаимно простое с p, то ap-1 ≡ 1 (mod p).
Действительно, раскрывая определение факториала, получаем:
(p - 1)! = 1·2·...·(p - 1) ≡ 1p-1 (mod p)
Прибавление 1 не меняет выполнение тождества по модулю p. Таким образом, теорема Вильсона является простым следствием малой теоремы Ферма.
Геометрическая интерпретация
Существует интересная геометрическая интерпретация теоремы Вильсона с использованием правильных многоугольников. Рассмотрим правильный n-угольник, вписанный в окружность. Если n является простым числом, то все его диагонали можно разбить на n групп, каждая из которых будет содержать по (n-1)! диагоналей. Это количество в точности соответствует утверждению теоремы!
История открытия
История теоремы Вильсона насчитывает уже более тысячи лет. Первое упоминание о ней встречается в трудах арабского математика Ибн аль-Хайсама примерно в 1000 г. н.э. Однако широкую известность она получила после публикации работы Эдварда Варинга в 1770 году, который приписал ее своему ученику Джону Вильсону.
Эта теорема впервые была сформулирована Ибн аль-Хайсамом около 1000 г.н.э, [1] и в 1770 году Варинг сформулировал эту теорему в своем сочинении «Meditationes Algebraicae», опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит его ученику Вильсону.
Первое доказательство теоремы в 1771 году дал выдающийся математик Жозеф Луи Лагранж.
Доказательство теоремы он опубликовал только в третьем издании своего Meditationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем.
В дальнейшем теорему Вильсона обобщили на случай составных модулей Эйлер и Гаусс. Наконец, Эйлер в «Opusc. Analyt.», Т. 1, р. 329 дал доказательство, Гаусс обобщил теорему Вильсона на случай составного модуля.
Доказательство теоремы
Рассмотрим доказательство теоремы Вильсона для простых и составных модулей.
Пусть p - простое число. Требуется доказать выполнение равенства:
(p - 1)! + 1 ≡ 0 (mod p)
- Заменим выражение (p-1)! через произведение целых чисел от 1 до p-1:
- Воспользуемся Малой теоремой Ферма, по которой если a взаимно просто с p, то ap-1 ≡ 1 (mod p)
- Так как p - простое, то все числа от 1 до p-1 взаимно просты с ним.
- Поэтому каждый множитель в выражении для факториала заменим на 1 по модулю p.
- Получаем: (p-1)! ≡ 1p-1 ≡ 1 (mod p)
- Прибавляя 1, окончательно имеем: (p-1)! + 1 ≡ 0 (mod p)
Теорема Вильсона для простых модулей доказана.
Подробное доказательство для школьников
Рассмотрим более подробное доказательство теоремы Вильсона, доступное для понимания школьников.
Пусть дано простое число p. Нам нужно показать, что факториал от p-1 плюс 1 делится нацело на p. Что такое факториал? Это произведение всех натуральных чисел от 1 до заданного числа. То есть:
(p-1)! = 1·2·3·...·(p-2)·(p-1)
Давайте посмотрим, какие числа входят в этот факториал. Все числа от 1 до p-1. Но если p - простое число, то все эти числа взаимно просты с ним! А теперь вспомним малую теорему Ферма. Она гласит, что если a взаимно просто с p, то ap-1≡1 (mod p).
Подставляя поочередно все числа из факториала вместо a, получаем:
1p-1≡1 (mod p)
2p-1≡1 (mod p) 3p-1≡1 (mod p) ... (p-1)p-1≡1 (mod p)
То есть каждый множитель в факториале в отдельности дает 1 по модулю p. Значит, и вся их произведение - тоже 1 по модулю p. Прибавляем 1 - получаем 0. Итак, мы доказали, что (p-1)! + 1 делится на p для любого простого числа p. Это и есть утверждение теоремы Вильсона!
Комбинаторное доказательство
Рассмотрим интересное комбинаторное доказательство теоремы Вильсона, не использующее ни факториалов, ни теоремы Ферма. Для этого воспользуемся следующим приемом.
Пусть дано простое число p. Возьмем числа от 1 до p-1 и расставим их по кругу в произвольном порядке. Теперь будем перемножать соседние числа, записывая произведения внутри круга. Повторим эту процедуру p-2 раза, до тех пор, пока внутри круга не останется одно число.
Давайте рассмотрим пример для p=5. Исходное расположение чисел может быть таким:
| 1 | 2 | 4 | 3 |
Перемножим соседние числа:
| 1 | 2 | 12 | 3 |
Еще раз:
| 1 | 2 | 12 | 36 |
И последний раз:
| 1 | 2 | 12 | 0 |
Получилось, что произведение всех чисел от 1 до p-1 дает 0 по модулю p. Прибавляя 1, получаем утверждение теоремы Вильсона. Таким образом, доказательство завершено!
Применение теоремы
Теорема Вильсона имеет важное прикладное значение. Рассмотрим некоторые аспекты ее использования.
Из теоремы Вильсона следует простой критерий проверки, является ли данное число p простым:
- Вычисляем выражение (p-1)! + 1
- Проверяем, делится ли оно нацело на p
- Если да - число p простое, если нет - составное
Данный критерий называется критерием Вильсона. Он позволяет определить простоту числа, не разлагая его на множители.
Кроме проверки простых чисел, теорему Вильсона можно использовать и для их генерирования. Для этого строится последовательность чисел вида:
n1 = 1 nk+1 = (nk - 1)! + 1
Согласно теореме Вильсона, каждый новый член этой последовательности будет простым числом.
Теорема Вильсона тесно связана с тестом Ферма - популярным вероятностным методом проверки чисел на простоту. Суть его состоит в следующем:
- Берется проверяемое число p и произвольное целое число a, меньшее p
- Проверяется выполнение равенства ap-1 ≡ 1 (mod p)
- Если равенство выполняется, то с некоторой вероятностью число p является простым
Как видно, в основе теста Ферма лежит малая теорема Ферма - то же соотношение, которое использовалось при доказательстве теоремы Вильсона.
Однако тест Ферма не является строгим, так как существуют псевдопростые числа, удовлетворяющие критерию Ферма, но не являющиеся по-настоящему простыми. Классическим примером служит составное число 561.
Теорема Вильсона в этом плане строже теста Ферма и позволяет отличить псевдопростые числа от истинно простых. Таким образом, эти два критерия хорошо дополняют друг друга.
