Math & Numbers

Проверка простоты по теореме Вильсона

Проверка простоты по теореме Вильсона: (n−1)! ≡ −1 (mod n) тогда и только тогда, когда n простое. Вычет (n−1)! mod n накапливается пошагово (n ≤ 10⁷), сверяется с детерминированным Миллером–Рабином, а для составных n проверяется факториальный закон (при n > 4 (n−1)! ≡ 0 (mod n), единственное исключение — n = 4). Может показать последовательность промежуточных произведений k! mod n (n ≤ 200).