Лучшие вопросы
Таймлайн
Чат
Перспективы

Теорема Вильсона

Из Википедии, свободной энциклопедии

Remove ads

Теорема Вильсона — теорема теории чисел, которая утверждает, что

Если — простое число, то число делится на .

Обратно: если делится на , то — простое число или 1.

Эта теорема, в основном, имеет теоретическое значение, поскольку факториал вычислить довольно трудно. Проще вычислить , поэтому элементарные тесты, определяющие, является ли число простым, основаны на теореме Ферма, а не на теореме Вильсона. Например, наибольшее простое число, найденное с использованием теоремы Вильсона, скорее всего — 1099511628401, и даже с оптимизированным подходом к расчёту потребуется около суток вычислений на процессорах SPARC, а числа с десятками тысяч цифр проходят тест на простоту с использованием теоремы Ферма меньше чем за час. Но, в отличие от малой теоремы Ферма, теорема Вильсона является одновременно необходимым и достаточным условием для простоты.

Remove ads

История

Эта теорема впервые была сформулирована Ибн аль-Хайсамом около 1000 г.н.э,[1] и в 1770 году Варинг сформулировал эту теорему в своём сочинении «Meditationes Algebraicae», опубликованном в Кембридже, где он привёл эту теорему без доказательства. По его словам, теорема принадлежит его ученику Вильсону[англ.]. Доказательство теоремы он опубликовал только в третьем издании своего Meditationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем[2]. Наконец, Эйлер в «Opusc. Analyt», Т. 1, р. 329 дал доказательство, Гаусс обобщил теорему Вильсона на случай составного модуля. Имеются данные о том, что Лейбниц знал о результате ещё столетием раньше, но никогда не публиковал его.

Remove ads

Пример

В таблице посчитаны значения для p от 2 до 37, а также остаток от деления на p (остаток от деления m на p обозначается как m mod p). Зелёным цветом выделены простые числа.

Подробнее , ...
Remove ads

Доказательство

Суммиров вкратце
Перспектива
Remove ads

Применение

Суммиров вкратце
Перспектива
  • Используем теорему Вильсона

Для нечётного простого p = 2m + 1, получаем

В результате

Мы можем использовать этот факт для доказательства известного результата: для любого простого p, такого что p ≡ 1 (mod 4) число (−1) является квадратом (квадратичный вычет) по модулю p. Действительно, пусть p = 4k + 1 для некоторого натурального k. Тогда m = 2k, следовательно

Теорема Вильсона используется для генерирования простых чисел, но она слишком медленная для практического применения.

Remove ads

Обобщение

Суммиров вкратце
Перспектива

Используя в качестве образца теорему Эйлера, попытаемся обобщить теорему Вильсона на случай p = n, где n — произвольное натуральное число. Простая замена (p − 1)! на произведение n1n2nk всех чисел, меньших n и взаимно простых с n, не проходит: в случае n = 8 это произведение равно 1 × 3 × 5 × 7 = 105, а 106 на 8 не делится. Но оказывается, что или n1n2nk + 1, или n1n2nk − 1 обязательно делится на n.

Рассмотрим множество En чисел, меньших n и взаимно простых с n. Под произведением двух элементов этого множества ab, будем понимать остаток от деления обычного произведения ab на n. Ясно, что если ab принадлежит En, то ab принадлежит En. Множество En относительно операции умножения является группой. В отличие от случая, когда n — простое, группа En может содержать элементы, не равные 1 и (n − 1) такие, что их квадрат равен 1: например если n = 8, то 3 × 3 = 1, 5 × 5 = 1, 7 × 7 = 1. Поэтому в общем случае произведение всех элементов из En не равно (n − 1). Покажем, что тогда оно равно 1.

Назовем элемент a группы En особым, если aa = 1. В этом случае элемент n − a — тоже особый. Следовательно, группа En содержит чётное число особых элементов: (a, n − a) — множество таких элементов, и никакой элемент не может быть парой сам для себя. Пусть n1, n2, …, nk — все элементы группы En, то есть полный набор чисел, меньших n и взаимно простых с n. Множество элементов, не являющихся особыми, разбивается на пары взаимно обратных, поэтому произведение таких элементов равно 1. С другой стороны, произведение особых элементов, составляющих пару (a, n − a), равно n − 1. Поскольку (n − 1)(n − 1) = 1, то произведение всех особых элементов равно 1 или n − 1, в зависимости от того, чётным или нечётным является число пар вида (a, n − a).ч. т. д.

Впервые теорема была доказана и обобщена Гауссом, при любом n > 2 для произведения всех натуральных чисел, не превосходящих n и взаимно простых с n, имеет место сравнение:

где  — нечётное простое число,  — натуральный показатель.

Позже было найдено ещё одно формальное обобщение теоремы Вильсона (В.Виноград):

При получается теорема Вильсона.

При получается , т.е.

, если

и

, если

Remove ads

См. также

Примечания

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads