Разложение числа на множители онлайн

Деление по модулю*

Давайте все-таки научимся не только умножать, но и делить по простому модулю. Вот только что это значит?

\(a / b\) = \(a \times b^{-1}\), где \(b^{-1}\) — это обратный элемент к \(b\).

Определение: \(b^{-1}\) — это такое число, что \(bb^{-1} = 1\)

Утверждение: в кольце остатков по простому модулю \(p\) у каждого остатка (кроме 0) существует ровно один обратный элемент.

Например, обратный к \(2\) по модулю \(5\) это \(3\) (\(2 \times 3 = 1 \pmod 5\)))

Задание

Найдите обратный элемент к: * числу \(3\) по модулю \(5\) * числу \(3\) по модулю \(7\) * числу \(1\) по модулю \(7\) * числу \(2\) по модулю \(3\) * числу \(9\) по модулю \(31\)

Давайте докажем это утверждение: надо заметить, что если каждый ненулевой остаток \(1, 2, \ldots, (p-1)\) умножить на ненулевой остаток \(a\), то получатся числа \(a, 2a, \ldots, (p-1)a\) — и они все разные! Они разные, потому что если \(xa = ya\), то \((x-y)a = 0\), а значит \((x — y) a\) делится на \(p\), \(a\) — ненулевой остаток, а значит \(x = y\), и это не разные числа. И из того, что все числа получились разными, это все ненулевые, и их столько же, следует, что это ровно тот же набор чисел, просто в другом порядке!

Из этого следует, что среди этих чисел есть \(1\), причем ровно один раз. А значит существует ровно один обратный элемент \(a^{-1}\). Доказательство закончено.

Это здорово, но этот обратный элемент еще хочется быстро находить. Быстрее, чем за \(O(p)\).

Есть несколько способов это сделать.

Через малую теорему Ферма

Малая теорема Ферма: > \(a^{p-1} = 1 \pmod p\), если \(p\) — простое, \(a \neq 0 \pmod p\)).

Доказательство: В предыдущем пункте мы выяснили, что множества чисел \(1, 2, \ldots, (p-1)\) и \(a, 2a, \ldots, (p-1)a\) совпадают. Из этого следует, что их произведения тоже совпадают по модулю: \((p-1)! = a^{p-1} (p-1)! \pmod p\).

\((p-1)!\neq 0 \pmod p\) а значит на него можно поделить (это мы кстати только в предыдущем пункте доказали, поделить на число — значит умножить на обратный к нему, который существует).

А значит, \(a^{p — 1} = 1 \pmod p\).

Как это применить Осталось заметить, что из малой теоремы Ферма сразу следует, что \(a^{p-2}\) — это обратный элемент к \(a\), а значит мы свели задачу к возведению \(a\) в степень \(p-2\), что благодаря быстрому возведению в степень мы умеем делать за \(O(\log p)\).

Обобщение У малой теоремы Ферма есть обобщение для составных \(p\):

Теорема Эйлера: > \(a^{\varphi(p)} = 1 \pmod p\), \(a\) — взаимно просто с \(p\), а \(\varphi(p)\) — это функция Эйлера (количество чисел, меньших \(p\) и взаимно простых с \(p\)).

Доказывается теорема очень похоже, только вместо ненулевых остатков \(1, 2, \ldots, p-1\) нужно брать остатки, взаимно простые с \(p\). Их как раз не \(p-1\), а \(\varphi(p)\).

Для нахождения обратного по этой теореме достаточно посчитать функцию Эйлера \(\varphi(p)\) и найти \(a^{-1} = a^{\varphi(p) — 1}\).

Но с этим возникают большие проблемы: посчитать функцию Эйлера сложно. Более того, на предполагаемой невозможности быстро ее посчитать построены некоторые криптографические алгоритм типа RSA. Поэтому быстро делить по составному модулю этим способом не получится.

Через расширенный алгоритм Евклида

Этим способом легко получится делить по любому модулю! Рекомендую.

Пусть мы хотим найти \(a^{-1} \pmod p\), \(a\) и \(p\) взаимно простые (а иначе обратного и не будет существовать).

Давайте найдем корни уравнения

\

Они есть и находятся расширенным алгоритмом Евклида за \(O(\log p)\), так как \(НОД(a, p) = 1\), ведь они взаимно простые.

Тогда если взять остаток по модулю \(p\):

\

А значит, найденный \(x\) и будет обратным элементом к \(a\).

То есть надо просто найти \(x\) из решения того уравнения по модулю \(p\). Можно брать по модулю прямо походу решения уравнения, чтобы случайно не переполниться.

Найти простое

Один из способов определения простого числа — «тест простоты». Если n — исследуемое число, то нужно попробовать разделить его на все числа больше 1 и меньше 1/2 n.

Самое большое обнаруженное простое число (на апрель 2015) содержит 17 425 170 знаков, это 257 885 161 – 1. Не стоит засиживаться до ночи, пытаясь выяснить следующее, если только вы не специализируетесь на этом, однако Фонд электронных рубежей (Electronic Frontier Foundation) назначил премию за первое простое число минимум в 100 миллионов знаков, а также за первое простое число минимум в пол миллиарда знаков.

Величайшие математические умы, а теперь еще и самые сложные компьютерные программы, давно пытаются найти закономерности в простых числах, но никакой предсказуемой закономерности до сих пор не было обнаружено.

Простые числа Мерсенна и Ферма

Формулы Миллса, Райта и другие подобные формулы остались изолированными фактами, не приведшими к новым результатам. Однако в других случаях возможность представить некоторые простые числа в том или ином специальном виде имеет неожиданные и глубокие следствия.

Рассмотрим сейчас две формулы, имеющие совсем простой вид:

p = 2n 1,	(8)
p = 2n + 1.	(9)

Очевидно, что формула (8) не всегда даёт простые числа; например, если n составное число, n = kl,k>1,l>1, то p делится на 2k  1 и на 2l  1. Но и при простом n получающееся по формуле (8) число может оказаться составным:

211 1 = 2047 = 23 · 89.

Простые числа, получающиеся по формуле (8), называются числами Мерсенна в честь Марена Мерсенна, который ещё в 1664 году указал все простые значения n, не превосходящие 257, для которых, по его мнению, формула (8) даёт простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным.

Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое число p имеет вид, указанный в формуле (8), то число p(p+1)/2 является совершенным. Например,

3 = 22 1,       7 = 23 1

простые числа, и соответственно

6 =	(3 · 4)/2 = 1 + 2 + 3,
28 =	(7 · 8)/2 = 1 + 2 + 4 + 7 + 14

совершенные числа. Спустя несколько столетий Леонард Эйлер доказал (попробуйте и здесь свои силы), что все чётные совершенные числа имеют вид, указанный Евклидом. Таким образом, вопрос, конечно или бесконечно множество чётных совершенных чисел, свёлся к вопросу, конечно или бесконечно множество простых чисел Мерсенна, то есть к вопросу, реализует ли формула (8) нашу программу-минимум. Ответ на этот вопрос не известен до сих пор .

Формула (9) также не всегда даёт простые числа, например, если n имеет простой нечётный делитель m, то p делится на 2n/m + 1, а если n само нечётно, то p делится на 3. Таким образом, вместо n в формулу (9) имеет смысл подставлять только 0 и степени числа 2. При n=0, 2, 21, 22, 23 и 24формула (9) действительно даёт простые числа, и Пьер Ферма, живший в XVII веке, высказал предположение, что и при любом nвида 2kформула (9) даёт простое число; в его честь простые числа вида 22k + 1 получили название чисел Ферма. Гипотезу Ферма опроверг Эйлер, указавший, что число 225 + 1 делится на 641. В настоящее время известно несколько значений nвида 2k, при которых по формуле (9) получаются составные числа, но не найдено ни одного нового простого числа Ферма, отличного от указанных выше.

Простые числа Ферма обнаруживают неожиданную связь с геометрией. Выдающийся немецкий математик Карл Фридрих Гаусс доказал, что правильный p-угольник можно построить циркулем и линейкой при простом p в том и только том случае, когда p число Ферма . Более общий результат таков: правильный m-угольник допускает построение циркулем и линейкой тогда и только тогда, когда m = 2s· p₁ p₂ …p_k , где p₁, p₂, …, p_k попарно различные простые числа Ферма.

Что такое разложение числа на множители?

Любое натуральное число можно представить в виде
произведения простых чисел. Это представление называется разложением
числа на простые множители.

Натуральное число называется делителем целого числа если для подходящего целого числа верно
равенство . В этом случае говорят, что делится на или что число кратно
числу .

Простым числом называют натуральное число , делящееся только на себя и на единицу. Составным
числом называют число, имеющее больше двух различных делителей (любое натуральное число не равное
имеет как минимум два делителя: и ). Например, числа – простые, а числа – составные.

Основная теорема арифметики. Любое натуральное число большее единицы, можно
разложить в произведение простых чисел, причём это разложение единственно с точностью до порядка следования
сомножителей.

Разложение на простые множители

Любое натуральное число можно разложить на произведение простых, и с такой записью очень легко работать при решении задач. Разложение на простые множители еще называют факторизацией.

\ \ \

Рассмотрим, например, такую задачу:

Условие: Нужно разбить \(N\) людей на группы равного размера. Нам интересно, какие размеры это могут быть.

Решение: По сути нас просят найти число делителей \(N\). Нужно посмотреть на разложение числа \(N\) на простые множители, в общем виде оно выглядит так:

\

Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень \(i\)-го простого число от 0 до \(a_i\) (то есть \(a_i+1\) различное значение), и так для каждого. То есть делитель \(N\) выглядит ровно так: \ Значит, ответом будет произведение \((a_1+1) \times (a_2+1) \times \ldots \times (a_k + 1)\).

Алгоритм разложения на простые множители

Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа \(N\), мы можем число \(N\) на него поделить и продолжить искать новый минимальный простой делитель.

Будем перебирать простой делитель от \(2\) до корня из \(N\) (как и раньше), но в случае, если \(N\) делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз (\(N\) может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда \(N\) стало либо \(1\), либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само \(N\) добавить в ответ.

Напишем алгоритм факторизации:

За сколько работает этот алгоритм?

Решение

За те же самые \(O(\sqrt{N})\). Итераций цикла while с перебором делителя будет не больше, чем \(\sqrt{N}\). Причем ровно \(\sqrt{N}\) операций будет только в том случае, если \(N\) — простое.

А итераций деления \(N\) на делители будет столько, сколько всего простых чисел в факторизации числа \(N\). Понятно, что это не больше, чем \(O(\log{N})\).

Разные свойства простых чисел*

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

• Простых чисел, меньших \(N\), примерно \(\frac{N}{\ln N}\).
• N-ое простое число равно примерно \(N\ln N\).
• Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
• Для любого \(N \ge 2\) на интервале \((N, 2N)\) всегда найдется простое число (Постулат Бертрана)
• Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить — это начать с \(N! + 2\).
• Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
• Максимальное число делителей равно примерно \(O(\sqrt{n})\). Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
• Максимальное число делителей у числа на отрезке \(\) — 128
• Максимальное число делителей у числа на отрекзке \(\) — 1344
• Максимальное число делителей у числа на отрезке \(\) — 103680
• Наука умеет факторизовать числа за \(O(\sqrt{n})\), но об этом как-нибудь в другой раз.
• Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.

Как разложить число на простые множители

Последовательность действий при разложении числа на простые множители:

1. Проверяем по таблице простых чисел, не является ли данное число простым.
2. Если нет, то последовательно подбираем самое маленькое простое число из таблицы простых чисел, на которое данное число делится без остатка, и выполняем деление.
3. Проверяем по таблице простых чисел, не является ли полученное частное простым числом.
4. Если нет, то последовательно подбираем самое маленькое простое число из таблицы простых чисел, на которое полученное частное делится нацело, и выполняем деление.
5. Повторяем пункты 3 и 4 до тех пор, пока в частном не получится единица.

Пример. Разложите число  102  на простые множители.

Решение:

Начинаем поиск наименьшего простого делителя числа  102.  Для этого последовательно подбираем самое маленькое простое число из таблицы простых чисел, на которое  102  разделится без остатка. Берём число  2  и пробуем разделить на него  102,  получаем:

102 : 2 = 51.

Число  102  разделилось на  2  без остатка, поэтому  2  — первый найденный простой множитель. Так как делимое равно делителю, умноженному на частное, то можно написать:

102 = 2 · 51.

Переходим к следующему шагу. Проверяем по таблице простых чисел, не является ли полученное частное простым числом. Число  51  составное. Начиная с числа  2,  подбираем из таблицы простых чисел наименьший простой делитель числа  51.  Число  51  не делится нацело на  2.  Переходим к следующему числу из таблицы простых чисел (к числу  3)  и пробуем разделить на него  51,  получаем:

51 : 3 = 17.

Число  51  разделилось на  3,  поэтому  3  — второй найденный простой множитель. Теперь мы можем и число  51  представить в виде произведения. Этот процесс можно записать так:

102 = 2 · 51 = 2 · 3 · 17.

Проверяем по таблице простых чисел, не является ли полученное частное простым числом. Число  17  простое. Значит наименьшим простым числом, на которое делится  17,  будет само это число:

17 : 17 = 1.

Так как в частном у нас получилась единица, то разложение закончено. Таким образом, разложение числа  102  на простые множители имеет вид:

102 = 2 · 3 · 17.

Ответ:  102 = 2 · 3 · 17.

В арифметике имеется ещё другая форма записи, облегчающая процесс разложения составных чисел. Она состоит в том, что весь процесс разложения записывают столбиком (в две колонки, разделённые вертикальной чертой). Слева от вертикальной черты, сверху вниз, записывают последовательно: данное составное число, затем получающиеся частные, а справа от черты — соответствующие наименьшие простые делители.

Пример. Разложить на простые множители число  120.

Решение:

Пишем число  120  и справа от него проводим вертикальную черту:

Справа от черты записываем самый маленький простой делитель числа  120:

Выполняем деление и получившееся частное  (60)  записываем под данным числом:

Подбираем наименьший простой делитель для  60,  записываем его справа от вертикальной черты под предыдущим делителем и выполняем деление. Продолжаем процесс до тех пор, пока в частном не получится единица:

В частном у нас получилась единица, значит разложение закончено. После разложения в столбик множители следует выписать в строчку:

120 = 23 · 3 · 5.

Ответ:  120 = 23 · 3 · 5.

Составное число разлагается на простые множители единственным образом.

Это значит, что если, например, число  20  разложилось на две двойки и одну пятёрку, то оно и всегда будет так разлагаться независимо от того, начнём ли мы разложение с малых множителей или с больших. Принято начинать разложение с малых множителей, т. е. с двоек, троек и т. д.

Есть работа

Простые числа пребывали в ленивом бездействии, пока не пришла необходимость в шифровании данных. Сейчас мы ежедневно посылаем несметное количество защищенных транзакций и других секретных данных через интернет, а простые числа предоставляют аналог защищенных фургонов, в которых перевозят данные. Начнем, перемножив два очень больших простых числа, чтобы получить составное число:

Р₁ х Р₂ = С

Составное число используется для генерации кода, который называется открытый ключ, который банк (или кто-нибудь) посылает человеку, желающему зашифровать свои данные. Если вы покупаете что-нибудь онлайн, данные вашей кредитки должны быть зашифрованы с использованием этого публичного ключа, шифрование происходит на вашем конце связи. Зашифрованные данные окажутся пустым набор слов, если будут перехвачены в процессе передачи. Когда данные вашей карты прибывают на другой конец, закрытый ключ — созданный из Р₁ и Р₂ — используется для расшифровки.

Это работает, так как очень сложно найти простые числа, из которых было получено составное, когда речь идет о больших числах. Любому хакеру понадобится 1000 лет компьютерного времени, чтобы взломать код и найти первоначальные простые числа. Именно потому, что так сложно взломать современный шифр, правительства скорее действительно предпочтут, чтобы разработчики встраивали «бэкдор» в свои системы, что позволяет им порой следить за тем, что делают люди.

Поделиться ссылкой

Простые и составные числа

Определение 1

Простыми числами являются целые числа, которые больше единицы и имеют только $2$ положительных делителя (само себя и $1$).

Определение 2

Составными числами являются целые числа, которые больше единицы и имеют не менее трех положительных делителей.

Замечание 1

Отметим, что число 1 – ни простое, ни составное. У единицы лишь один положительный делитель – это само число $1$.

Т.к. целыми положительными числами являются натуральные числа, а у единицы только один положительный делитель, то можно сформулировать следующие определения простых и составных чисел.

Статья: Простые и составные числа, разложение на множители

Найди решение своей задачи среди 1 000 000 ответов

Определение 3

Простыми числами называются натуральные числа, у которых только $2$ положительных делителя.

Определение 4

Составными числами называются натуральные числа, у которых больше двух положительных делителей.

Пример 1

Примером простых чисел являются числа $2$, $7$, $11$, $17$, $19$, $29$, $131$, $523$. Для данных чисел невозможно подобрать какой-нибудь положительный делитель, который отличается от единицы и самого этого числа.

Пример 2

Примером составных чисел являются числа $8$, $51$, $100$. У числа $8$ кроме положительных делителей $1$ и $8$ есть делители $2$ и $4$, т.к. $8=2\cdot 4$, поэтому $8$ является составным числом.

У числа $51$ есть положительные делители $1$, $3$, $17$ и $51$. Число $100$ имеет положительные делители $1, 2, 4, 5, 10, 20, 25, 50$ и $100$.

Любое составное число может быть разложено на $2$ множителя, больших $1$.

Пример 3

Например, $9=3\cdot 3$, $36=2\cdot 2\cdot 3\cdot 3$, $66=2\cdot 3\cdot 11$ и т.д.

Замечание 2

Простое число на $2$ множителя, больших $1$, разложить нельзя.

Замечание 3

Существует таблица простых чисел, которую используют для удобства дальнейшего использования простых чисел.

НОВОСТИ 2021 (рекорды и значимые события):

2021.11.24 — Gary Gostin нашел делитель 205071338665 *2^1382 +1 числа Ферма F1379 (360-й известный делитель)

2021.11.14 — fobius (PrimeGrid) нашел 19-значную прогрессию AP24

2021.10.18 — Ryan Propper & Serge Batalov нашли 1.888.529-значный Near-repdigit & палиндром 10^1888529 -10^944264 -1

2021.10.03 — jpldcon4 (PrimeGrid) нашел 19-значную прогрессию AP24

2021.09.27 — James Winskill нашел 1.418.398-значный праймориал 3267113# -1

2021.09.24 — Serge Batalov нашел 884.748-значную прогрессию AP3

2021.09.23 — Serge Batalov нашел 807.954-значную прогрессию AP3

2021.09.18 — Laurent Facq & Jared Asuncion & Bill Allombert нашли 30.949-значное PRP число Фиббоначи U(148091)

2021.09.15 — Ryan Propper & Serge Batalov нашли 1.234.567-значный палиндром 10^1234567 -20342924302*10^617278 -1

2021.08.28 — Tom Greer нашел 4.705.888-значное Generalized Cullen 2525532 *73^2525532 +1

2021.08.25 — Tuna Ertemalp (PrimeGrid) нашла 19-значную прогрессию AP25

2021.08.03 — Laurent Facq & Jared Asuncion & Bill Allombert нашли 28.709-значное PRP Wagstaff (2^95369 +1)/3

2021.08.12 — Erwin Doescher нашел делитель 749893 *2^66648 +1 числа Ферма F66643 (359-й известный делитель)

2021.08.06 — Makoto Morimoto нашел 490.001-значный палиндром 10^490000 +3*(10^7383 -1)/9 *10^241309 +1

2021.07.31 — Tuna Ertemalp (PrimeGrid) нашла 19-значную прогрессию AP26

2021.07.08 — Tuna Ertemalp (PrimeGrid) нашла 19-значную прогрессию AP24

2021.06.09 — jpldcon4 (PrimeGrid) нашел 19-значную прогрессию AP25

2021.05.14 — j.sheridan (PrimeGrid) нашел 19-значную прогрессию AP24

2021.05.08 — Ryan Propper & Serge Batalov нашли 8.177.207-значный PRP Repunit (10^8177207 -1)/9

2021.05.04 — Jared Asuncion & Bill Allombert нашли 27.173-значное PRP число Фиббоначи U(130021)

2021.05.04 — Tuna Ertemalp (PrimeGrid) нашел 19-значную прогрессию AP25

2021.04.20 — Ryan Propper & Serge Batalov нашли 5.794.777-значный PRP Repunit (10^5794777 -1)/9

2021.03.27 — jpldcon4 (PrimeGrid) нашел 19-значную прогрессию AP25

2021.03.14 — Bikermatt (PrimeGrid) нашел 19-значную прогрессию AP24

2021.03.10 — Ryan Propper & Serge Batalov нашли 4.143.644-значное Generalized Cullen 404849 *2^13764867 +1

2021.03.04 — Gary Gostin нашел делитель 14698299 *2^25602 +1 числа Ферма F25599 (358-й известный делитель)

2021.03.02 — Vincent Diepeveen & Tony Reix & Paul Underwood & Jeff Gilchrist нашли 4.027.872-значное PRP 2^13380298 -27

2021.03.01 — Luigi Morelli нашел делитель 74327396788321657 *2^42 +1 числа Ферма F40 (357-й известный делитель)

2021.02.17 — Tom Greer нашел 2.599.757-значный делитель 17 *2^8636199 +1 обобщенного числа Ферма GF(8636198,10)+…

2021.01.16 — Tom Greer нашел делитель 27 *2^7963247 +1 числа Ферма F7963245 (356-й известный делитель)

2021.01.16 — jpldcon4 (PrimeGrid) нашел 19-значную прогрессию AP24

2021.01.12 — vanos0512 (PrimeGrid) нашел 19-значную прогрессию AP24

История

То, что существуют числа, которые не делятся ни на какое другое число, люди знали еще в древности. Последовательность простых чисел имеет примерно следующий вид:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Доказательство того, что этих чисел бесконечно много, дал еще Евклид, живший в 300 г до н.э. Примерно в те же годы другой греческий математик, Эратосфен, придумал довольно-таки простой алгоритм получения простых чисел, суть которого была в последовательном вычеркивании чисел из таблицы. Те оставшиеся числа, которые ни на что не делились, и были простыми. Алгоритм называется «решето Эратосфена» и за счет своей простоты (в нем нет операций умножения или деления, только сложение) используется в компьютерной технике до сих пор.

Видимо, уже во время Эратосфена стало ясно, что какого-либо четкого критерия, является ли число простым, не существует — это можно проверить лишь экспериментально. Существуют различные способы для упрощения процесса (например, очевидно, что число не должно быть четным), но простой алгоритм проверки не найден до сих пор, и скорее всего найден не будет: чтобы узнать, простое число или нет, надо попытаться разделить его на все меньшие числа.

Подчиняются ли простые числа каким-либо законам? Да, и они довольно любопытны.

Так, например, французский математик Мерсенн еще в 16 веке обнаружил, что много простых чисел имеет вид 2^N — 1, эти числа названы числами Мерсенна. Еще незадолго до этого, в 1588 году, итальянский математик Катальди обнаружил простое число 219 — 1 = 524287 (по классификации Мерсена оно называется M19). Сегодня это число кажется весьма коротким, однако даже сейчас с калькулятором проверка его простоты заняла бы не один день, а для 16 века это было действительно огромной работой.

На 200 лет позже математик Эйлер нашел другое простое число 231 — 1 = 2147483647. Опять же, необходимый объем вычислений каждый может представить сам. Он же выдвинул гипотезу (названную позже «проблемой Эйлера», или «бинарной проблемой Гольдбаха»), суть которой проста: каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Например, можно взять 2 любых четных числа: 123456 и 888777888.

С помощью компьютера можно найти их сумму в виде двух простых чисел: 123456 = 61813 + 61643 и 888777888 = 444388979 + 444388909. Интересно здесь то, что точное доказательство этой теоремы не найдено до сих пор, хотя с помощью компьютеров она была проверена до чисел с 18 нулями.

Существует и другая теорема математика Пьера Ферма, открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4*k+1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4*111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197*19197 + 8710*8710.

Теорема была доказана Эйлером лишь через 100 лет.

И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.

Так что с простыми числами не все так просто. Есть и удивительные факты. Например, в 1883 г. русский математик И.М. Первушин из Пермского уезда доказал простоту числа 261 — 1 = 2305843009213693951. Даже сейчас бытовые калькуляторы не могут работать со столь длинными числами, а на то время это была поистине гигантская работа, и как это было сделано, не очень ясно до сих пор. Хотя действительно существуют люди, обладающие уникальными способностями мозга — так например, известны аутисты, способные находить в уме (!) 8-значные простые числа. Как они это делают, непонятно.

Кратные числа

Если какое-нибудь число без остатка разделилось на другое, то его называют кратным этого числа. Например, 6 без остатка делится на 3. Поэтому 6 является кратным числа 3

6 : 3 = 2

Определение. Кратным числа а называется число, которое делится без остатка на а.

Данное определение содержит переменную a. Подставим вместо этой переменной любое число, например число 5 и прочитаем определение:

Кратным числа 5 называется число, которое делится без остатка на 5.

У любого числа бесконечно много кратных. Например, первыми кратными числа 5, являются числа 5, 10, 15, 20, 25. Все они кратны 5, поскольку делятся на 5 без остатка:

5 : 5 = 110 : 5 = 215 : 5 = 320 : 5 = 425 : 5 = 5

Какие числа простые, а какие составные: примеры

Чтобы выяснить, какие числа простые, а какие составные, оптимальным решением станет использование признаков делимости. Более подробно можно рассмотреть это на Примере 1:

Пример 1

Необходимо доказать, что число 696969696969696969 является составным.

Решение

Сумма цифр данного числа будет равняться 9 ⋅ 6 + 9 ⋅ 9 = 9 ⋅ 15. Из этого следует, что для числа 9 ⋅ 15, 9 и 15 будут являться простыми делителями составного числа. Соответственно, число является составным и имеет как минимум три делителя.

Но, если необходима будет проверка, то следует использовать другие действия. Оптимальным способом станет числовой перебор. В процессе могут быть найдены составные и простые числа, которые не должны превосходить квадратный корень из а. Число разлаживается на простые множители. Если данное условие будет выполнено, значит, его можно считать простым.

Признаки делимости

Для начала давайте вспомним: как определить, на что делится число? Рассмотрим таблицу признаков делимости. Эти признаки лучше запомнить!

Признак делимости на	Правило	Примеры
2	Число четное, оканчивается на 0, 2, 4, 6, 8	10,  10482: 10 : 2 = 5; 10482 : 2 = 5241
3	Сумма цифр делится на 3	42, 201: 42 : 3  (сумма чисел 4 + 2 = 6), а 6 делится на 3, значит, 42 делится на 3; 201 : 3 (сумма чисел 2 + 1 = 3), а 3 делится на 3, значит, и 201 делится на 3
4	Последние две цифры либо нули, либо образуют число, которое делится на 4	200, 1016: 200 : 4 = 50; 1016( последние два числа 16, 16 делится на 4), значит, и 1016 : 4 = 254
5	Оканчивается на 0 или 5	10, 205: 10 : 5 = 2; 205 : 5 = 41;
6	Делится на 2 и на 3	42: делится на 2, так как является четным; делится на 3, так как сумма цифр 4 + 2 = 6 делится на 3 24: делится на 2, так как является четным; делится на 3, так как сумма цифр 2 + 4 = 6 делится на 3
7	Разность числа без последней цифры и удвоенной последней цифры делится на 7	392: 39 − (2 × 2) = 39 − 4 = 35; 35 делится на 7, значит, и 392 : 7 = 56
8	Последние три цифры либо нули, либо образуют число, которое делится на 8	15000 : 8 = 1875; 1640 : 8 = 205;
9	Сумма цифр делится на 9	522 делится на 9, так как 5 + 2 + 2 = 9; 1782 делится на 9, так как 1 + 7 + 8 + 2 = 18
10	Оканчивается на 0	30 : 10 = 3; 24580 : 10 = 2458