Рубрики

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

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


    (p - 1) ! ≡  -1   mod p 
OR  (p - 1) ! ≡  (p-1) mod p
 

Примеры:

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

p  = 7
(p-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, поэтому мы не можем иметь (р-1)! = -1 (мод р).

3) Теперь давайте посмотрим, как именно это -1, когда р простое число. Если 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 », что это для деталей).

Смотрите это для большего применения теоремы Вильсона.

Ссылки:
https://en.wikipedia.org/wiki/Wilson's_theorem
https://primes.utm.edu/notes/proofs/Wilsons.html

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes