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

Опубликовано: 21 Января, 2022

Теорема Вильсона утверждает, что натуральное число p> 1 является простым числом тогда и только тогда, когда


    (п - 1)! ≡ -1 mod p 
ИЛИ (p - 1)! ≡ (p-1) mod p

Примеры:

р = 5
(р-1)! = 24
24% 5 = 4

р = 7
(р-1)! = 6! = 720
720% 7 = 6

Как это работает?
1) Мы можем быстро проверить результат для p = 2 или p = 3.

2) Для p> 3: если p составное, то его положительные делители находятся среди целых чисел 1, 2, 3, 4,…, p-1, и ясно, что gcd ((p-1) !, p)> 1, поэтому у нас не может быть (p-1)! = -1 (по модулю p).

3) Теперь посмотрим, как это в точности равно -1, когда p простое число. Если p простое, то все числа в [1, p-1] взаимно просты с p. И для каждого числа x в диапазоне [2, p-2] должна существовать пара y такая, что (x * y)% p = 1. Итак

    [1 * 2 * 3 * ... (p-1)]%p 
 =  [1 * 1 * 1 ... (p-1)] // Group all x and y in [2..p-2] 
                          // such that (x*y)%p = 1
 = (p-1)

Чем это может быть полезно?
Рассмотрим задачу вычисления факториала по модулю простого числа, которое близко к входному числу, т. Е. Мы хотим найти значение «n! % p », такое что n <p, p простое число и n близко к p. Например (25!% 29). Из теоремы Вильсона мы знаем, что 28! равно -1. Таким образом, нам в основном нужно найти [(-1) * inverse (28, 29) * inverse (27, 29) * inverse (26)]% 29. Обратная функция inverse (x, p) возвращает значение, обратное x по модулю p. (Подробнее см. Здесь).

См. Здесь, чтобы узнать о других приложениях теоремы Вильсона.

Использованная литература:
https://en.wikipedia.org/wiki/Wilson's_theorem
https://primes.utm.edu/notes/proofs/Wilsons.html

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ