Просмотр кода страницы Обсуждение:Простое число

{{Ежегодные просмотры}}
{{Сообщение ЗЛВ|даты=3—6 марта 2018 года|текст=[[Фонд электронных рубежей|Некоммерческая организация]] обещает заплатить $250 000 за сообщение '''[[Простое число|некоторой комбинации цифр]]'''.|архив=2018-03#3—6 марта|иллюстрация=}}
{{10000}}
{{Не форум}}
{{Статья проекта Математика|важность=высшая|уровень=I}}
{{Статья проекта Числа|важность=высшая|уровень=I}}
{{Сообщение ИС|9 сентября 2004|Простое число|Лишена|23 ноября 2006}}
{{Сообщение ХС|23 ноября 2006|28 ноября 2006|Лишена|2012/1}}
{{Сообщение ЗЛВ | даты=25-28 декабря 2005 года | текст=[[15 декабря]] [[2005]] года было найдено очередное наибольшее '''[[простое число]]''': 2<sup>30402457</sup>&nbsp;&minus;&nbsp;1 | архив=2005-12#25—28 декабря}}
{{Сообщение ДС|16 декабря 2017|16 декабря 2017|Кандидат в ХС/ИС}}
{{Архив|2004-2015}}

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

<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|Amanda Sproule}} 16:14, 17 декабря 2018‎ (UTC)

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

[[У:LGB|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|Amanda Sproule]] ([[ОУ:Amanda Sproule|обс.]]) 23:05, 26 декабря 2018 (UTC)

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

Русское предложение '''"Число n - простое."''' равносильно математическому предложению '''n &isin; &Nopf;\{0, 1} &and; {x| x &isin; &Nopf;\{0} &and; n mod x = 0} = {1, n}'''.

Русское предложение '''"Число n - чётно."''' равносильно математическому предложению '''n &isin; &Nopf; &and; n mod 2 = 0'''.

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