Как доказать что число простое

Определение. Число р О N , р № 1, называется простым, если р имеет в точности два положительных делителя: 1 и р . Остальные натуральные числа (кроме 1) принято называть составными. Число 1 — на особом положении, по договору, оно ни простое, ни составное.

Как это часто бывает в математике, да и в других науках, прилагательным «простой» называется объект только первоначально казавшийся простым. Простые числа, как выяснилось в процессе накопления научных знаний, появляются в различных областях математики и являются одним из самых загадочных и тяжелых для изучения монстров. Любопытного читателя, любителя ужастиков и лихо закрученных сюжетов, я отсылаю здесь к изумительному рассказу математика из Боннского университета Дон Цагира «Первые пятьдесят миллионов простых чисел», опубликованному в книжке «Живые числа», М.: Мир, 1985 г.

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

Наблюдение 1. Наименьший делитель любого числа а О N , отличный от 1, есть число простое.

Доказательство. Пусть с | а , с № 1 и с — наименьшее с этим свойством. Если существует с 1 такое, что с 1 | с , то с 1 Ј с и с 1 | а , следовательно, с 1 = с или с 1 = 1.

Наблюдение 2. Наименьший отличный от 1 делитель составного числа а О N не превосходит Ц a .

Доказательство. с | а , с № 1, с — наименьший, следовательно

а = са 1 , а 1 | а , а 1 і с , значит аа 1 і с 2 а 1 , а і с 2 и с Ј Ц a .

Следующее наблюдение, отдавая дань уважения его автору — Евклиду, назовем теоремой.

Теорема (Евклид). Простых чисел бесконечно много.

Доказательство. От противного. Ну пусть р 1 , р 2 . р n — все простые, какие только есть. Рассмотрим число а = р 1 р 2 . р n + 1. Его наименьший отличный от 1 делитель с , будучи простым, не может совпадать ни с одним из р 1 , р 2 . р n , так как иначе с | 1. Не перестаю удивляться изобретательности ума людей тысячелетней древности!

Для составления таблицы простых чисел древний грек Эратосфен придумал процедуру, которая получила название «решето Эратосфена»:

2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13, 14 , 15 , 16 , 17.

Идем по натуральному ряду слева направо. Подчеркиваем первое неподчеркнутое и невычеркнутое число, а из дальнейшего ряда вычеркиваем кратные только что подчеркнутому. И так много раз. Легко понять, что подчеркнутые числа — простые. Если вспомнить наблюдение 2, то становится понятно, что когда вычеркнуты все кратные простых, меньших р , то оставшиеся невычеркнутые, меньшие р 2 — простые. Это значит, что составление таблицы всех простых чисел меньших N закончено сразу, как только вычеркнуты все кратные простых, меньших Ц a .

Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Чудаки люди! Например, в 1876 году француз Люка доказал, что число 2 127 — простое, и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если на него взглянуть:

2 127 -1 = 170141183460469231731687303715884105727.

В настоящее время составлены таблицы всех простых чисел, не превосходящих 50 миллионов, далее известны только отдельные их представители. Читателей всегда привлекает гигантизм, поэтому укажу здесь два самых больших известных на сегодняшний момент простых числа: 2 44497 — 1 и 2 86243 — 1. Последнее число записано пока в книгу рекордов Гиннеса, в нем 25962 десятичных знака. Найдено оно было, конечно, в рекламных целях — демонстрация фирмой IBM возможностей очередного суперкомпьютера, которому для проверки этого числа на простоту с помощью специальных изощренных тестов (пригодных только для чисел вида 2 n- 1) потребовалась неделя работы и куча денег. И это трата денег происходит в то время, когда у нас в России более трети населения живет за чертой бедности, а половина детей в Уганде не умеют ни читать, ни писать, а только сидят и гундят!

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

Теорема. Всякое целое число, отличное от — 1, 0 и 1, единственным образом (с точностью до порядка сомножителей) разложимо в произведение простых чисел.

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

Пусть а > 1, р 1 — его наименьший простой делитель. Значит,

а = р 1 а 1 . Если, далее, а 1 > 1, то пусть р 2 — его наименьший простой делитель и а 1 = р 2 а 2 , т.е. а = р 1 р 2 а 2 , и так далее, пока а n не станет равным единице. Это обязательно произойдет, так как а > а 1 > а 2 . а натуральные числа с естественным порядком удовлетворяют условию обрыва убывающих цепей (во как выразился!). Имеем, таким образом,

a = p 1 p 2 . p n , и возможность разложения доказана.

Покажем единственность. Ну пусть a = q 1 q 2 . q n — другое разложение, т.е. p 1 p 2 . p n = q 1 q 2 . q s . В последнем равенстве правая часть делится на q 1 , следовательно, левая часть делится на q 1 . Покажем, что если произведение p 1 p 2 . p n делится на q 1 , то один из сомножителей р k обязан делиться на q 1 .

Действительно, если q 1 | p 1 , то все доказано. Пусть q 1 не делит p 1 . Так как q 1 — простое число, то ( q 1 , p 1 ) = 1. Значит найдутся такие

u , v О Z , что up 1 + vq 1 = 1. Умножим последнее равенство на p 2 . p n , получим: p 2 . p n = p 1 ( p 2 . p n ) u + q 1 ( p 2 . p n ) v . Оба слагаемых справа делятся на q 1 , следовательно, p 2 . p n делится на q 1 . Далее рассуждайте по индукции сами.

Теперь пусть, например, q 1 | p 1 . Значит q 1 = p 1 , так как p 1 — простое. Из равенства p 1 p 2 . p n = q 1 q 2 . q s банальным сокращением моментально получим равенство p 2 . p n = q 2 . q s . Снова рассуждая по индукции, видим, что n = s , и каждый сомножитель левой части равенства p 1 p 2 . p n = q 1 q 2 . q n обязательно присутствует в правой и наоборот.

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

Следствие 1. Всякое рациональное число однозначно представимо в виде

a 1
1

a 2
2

. p

a k
k

где a 1 , a 2 . a k О Z .

Теоремы о простых числах

Теорема о существовании бесконечного числа простых чисел

Простых чисел бесконечно много.

Теорема о расходимости ряда [math]\sum_<>^<>1/n[/math]

Ряд [math]\sum_<>^<>1/n[/math] расходится.

Заметим для некоторого [math]k[/math] : [math]\sum_

^<><(1 + \frac

+ \frac + \cdots)> \ge \sum_ \frac[/math] . Теперь, пользуясь выражением [math] \ln(1+x) \approx x + o(x) [/math] и логарифмируя, выводим: [math] \sum_

<\ln(1 + \frac

+ \frac + \cdots)> \approx \sum_

< (\frac

+ \frac + \cdots)> \le \frac [/math] — расходится.

Теорема о расходимости ряда [math]\sum_<>^<>1/p[/math]

Ряд [math]\sum_<>^<>1/p[/math] , где [math]p[/math] — простое, расходится.

Работая в условиях предыдущей теоремы, продолжаем: [math] \ln(1+x) \le x[/math] , тогда [math] \sum_<>^<> <\ln(1 + \frac

+ \cdots)> \le \sum_<>^<> <( \frac

+ \frac + \cdots)>[/math] .

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

Простые числа — натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x.

Например, 11 — это простое число. Его можно разделить только на 1 и 11. Деление простого числа на другое приводит к тому, что остается остаток, что называют простым числом. 13 ÷ 4 = 3 (остаток 1). Число, имеющее более двух множителей, называется составными числами. Наименьшее простое число равно 2, потому что оно делится само на себя и только на 1.

30 не является примером простого числа, потому что его можно разделить на 1,2,3,5,6,10,15,30. Таким образом, 30 является примером составного числа, поскольку оно имеет более двух факторов. Ноль, единица и числа меньше единицы не считаются простыми числами.

Основная теорема арифметики, лемма Евклида

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

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

Фундаментальная теорема арифметики (название которой указывает на ее основную важность) гласит, что любое число может быть учтено в уникальном списке простых чисел. Пример 3

10 равно 2×5;
11 — простое число;
12 — 2×2×3;
13 — это простое число;
14 равно 2×7;
15 равно 3×5;
16 равно 2×2×2×2;
17 является простым и т.д.

Таким образом, они либо простые, либо простые числа, умноженные друг на друга.

Число 42. Можем ли мы получить 42, умножив только простые числа?

Да, 2, 3 и 7 являются простыми числами, и при умножении вместе они составляют 42.

Число 7. 7 уже является простым числом

Число 22. 22 может быть получено путем умножения простых чисел 2 и 11 вместе.

Никакая другая комбинация простых чисел не будет работать.

Лемма — это, как правило, незначительное, доказанное утверждение, которое используется в качестве ступеньки к доказательству более сложной математической теории. По этой причине она также известна как «вспомогательная теорема».

В теории чисел лемма Евклида — это лемма, которая отражает фундаментальное свойство простых чисел, а именно: если простое число p делит произведение ab двух целых чисел a и b, то p должно разделить, по крайней мере, одно из этих целых чисел a и b.

Если p = 19, a = 133, b = 143, то ab = 133 × 143 = 19019, и поскольку это делится на 19, лемма подразумевает, что один или оба из 133 или 143 также должны быть. На самом деле 133 = 19 × 7.

Если предпосылка леммы не выполняется, т. е. p является составным числом, его следствие может быть либо истинным, либо ложным.

В случае p = 10, a = 4, b = 15 составное число 10 делит ab = 4 × 15 = 60, но 10 не делит ни 4, ни 15.

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

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

Как определить простые числа

Сначала попробуйте разделить его на 2 и посмотреть, получится ли целое число. Если да, то оно не может быть простым числом. Если вы не получите целое число, затем попробуйте разделить его на простые числа: 3, 5, 7, 11 (9 делится на 3) и так далее, всегда делясь на простое число.

8 простых чисел до 20: 2, 3, 5, 7, 11, 13, 17 и 19.

Первые 10 простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Таблица простых чисел до 1000:

2	3	5	7	11	13	17	19	23
29	31	37	41	43	47	53	59	61	67
71	73	79	83	89	97	101	103	107	109
113	127	131	137	139	149	151	157	163	167
173	179	181	191	193	197	199	211	223	227
229	233	239	241	251	257	263	269	271	277
281	283	293	307	311	313	317	331	337	347
349	353	359	367	373	379	383	389	397	401
409	419	421	431	433	439	443	449	457	461
463	467	479	487	491	499	503	509	521	523
541	547	557	563	569	571	577	587	593	599
601	607	613	617	619	631	641	643	647	653
659	661	673	677	683	691	701	709	719	727
733	739	743	751	757	761	769	773	787	797
809	811	821	823	827	829	839	853	857	859
863	877	881	883	887	907	911	919	929	937
941	947	953	967	971	977	983	991	997

2 — наименьшее простое число. Это также единственное четное простое число — все остальные четные числа могут быть разделены сами по себе на 1 и 2, что означает, что у них будет, по крайней мере, 3 фактора.

Один из самых известных математиков классической эпохи, Евклид, записал доказательство того, что не существует самого большого простого числа. Самое большое известное простое число (по состоянию на ноябрь 2020 года) составляет 282 589 933-1, число, которое имеет 24 862 048 цифр при записи в базе 10. До этого самым большим известным простым числом было 277 232 917-1, состоящее из 23 249 425 цифр.

За исключением 2 и 3, все остальные простые числа могут быть выражены в общей форме как 6n + 1 или 6n — 1, где n — натуральное число.

Чтобы определить, является ли число простым или составным, нужно решить пример на делимость в следующем порядке (от простого к сложному): 2, 5, 3, 11, 7, и 13. Если вы обнаружите, что число делится на одно из них, и вы знаете, что оно составное, не нужно выполнять остальные тесты.

Если число меньше 121 не делится на 2, 3, 5 или 7, оно простое; в противном случае оно составное.

Если число меньше 289 не делится на 2, 3, 5, 7, 11, или 13, это простое число; в противном случае оно составное.

Примеры решения задач

Является ли 19 простым числом или нет?

Как понять, что число простое можно двумя способами.

Формула для простого числа равна 6n + 1

Запишем данное число в виде 6n + 1.

6(3) + 1 = 18 + 1 = 19

Проверьте на наличие факторов 19

Следовательно, с помощью обоих методов докажем, что 19 имеет только два фактора 1 и 19, что означает простое число.

53 — это простое число или нет?

Как доказать, что число простое, используя приведенную ниже формулу. Чтобы узнать простые числа, превышающие 40, можно:

n2 + n + 41, где n = 0, 1, 2, . 39

32 + 3 + 41 = 9 + 3 + 41 = 53

53 имеет только факторы 1 и 53.

Итак, 53 является простым числом по обоим методам.

Является ли число простым или составным?

Число 185 заканчивается на 5, поэтому оно делится на 5. Оно составное.

Как проверить простое ли число 243?

Число 243 заканчивается нечетным числом, поэтому оно не делится на 2. Он не заканчивается на 5 или 0, поэтому он не делится на 5. Его цифровой корень равен 9 (потому что 2 + 4 + 3 = 9), так что оно делится на 3.

243/3 = 81. Оно является составным.