Обсуждение:Простое число

Проверка свойства простоты

${\displaystyle (n-1)!\equiv (n-1){\pmod {n}}}$ - число n является простым если удовлетворяет сравнению.

Пример: n = 17

16! === 16 mod 17

20922789888000 mod 17 = 16 (17 - простое число)

Пример2: n = 15

14! === 14 mod 15

87178291200 mod 15 = 0 (15 составное, так как не удовлетворяет сравнению по модулю) -- Amanda Sproule 16:14, 17 декабря 2018‎ (UTC)

Это одна из форм теоремы Вильсона. Практическое применение такого правила крайне затруднено тем, что факториал при n > 100 принимает чудовищно большие значения. LGB (обс.) 16:30, 17 декабря 2018 (UTC)

LGB - спасибо за наводку, тут еще парочка видов теоремы Вильсона есть.

${\displaystyle (n-2)!\equiv 1{\pmod {n}}}$ - число n является простым если удовлетворяет сравнению.

Можно еще сократить сложность вычисления факториала если отнять от $n$ целую часть корня из ${\sqrt {n}}$.

${\displaystyle (n-{\sqrt {n}})!\not \equiv 0{\pmod {n}}}$ - число n является простым если удовлетворяет сравнению.

Amanda Sproule (обс.) 23:05, 26 декабря 2018 (UTC)