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

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

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

Пример: n = 17

16! === 16 mod 17

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

Пример2: n = 15

14! === 14 mod 15

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

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

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

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

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

<math>{\displaystyle (n - \sqrt{n})! \not \equiv 0 {\pmod {n}}}</math> - число n является простым если удовлетворяет сравнению -- Amanda Sproule (обс.) 23:05, 26 декабря 2018 (UTC)

О математической формулировке понятия "простое число"

Русское предложение "Число n - простое." равносильно математическому предложению n ∈ ℕ\{0, 1} ∧ {x| x ∈ ℕ\{0} ∧ n mod x = 0} = {1, n}.

Русское предложение "Число n - чётно." равносильно математическому предложению n ∈ ℕ ∧ n mod 2 = 0.

Из изложенного выше следует, что понятие "простое число" гораздо сложнее понятия "чётное число". 188.242.111.10 19:45, 17 декабря 2025 (UTC)