Доказательство.

Пусть d = (а, р) => (a /d) & (р /d), т.к. р - простое число, то оно имеет два делителя 1 и р. Если (а, р) = 1, то а и р взаимно просты, если (а, р) = р, то (а/р).

Задача 2. Если произведение нескольких сомножителей делится на р, то по крайней мере один из сомножителей делится на р.

Решение.

Пусть произведение (а12,...,аk)/р, если все ai не будут делиться на р, тогда и произведение будет взаимно просто с р, следовательно, какой-то сомножитель делится на р.

Задача 3. Доказать, что наименьший отличный от 1 делитель целого числа а>1, есть число простое.

Доказательство.

Пусть aÎZ и а - составное число (если а = р, то утверждение доказано), тогда а = a1q.

Пусть q - наименьший делитель, покажем, что он будет простым числом. Если предположить, что q - составное число, тогда q = q1k и а = a1•q1k, т.к. q1<q, то q - уже не будет наименьшим делителем, что противоречит условию задачи. Следовательно, q - простое число.

Задача 4. Доказать, что наименьший простой делитель (р) натурального числа (n) не превосходит Ön .

Доказательство.

Пусть n = рn1, причем р < n1 и р - простое. Тогда n ³ р2 => р<Ön .

Из этого утверждения следует, что если натуральное число (n) не делится ни на одно простое число р £Ön , то n – простое, в противном случае оно будет составным.

Пример 1. Выяснить, будет ли число 137 простым? 11 <Ö137 <12.

Выписываем простые делители, не превосходящие Ö137: 2, 3, 5, 7, 11. Проверяем, что 137 не делится на 2, на 3, на 5, на 7, на 11. Следовательно, число 137 – простое.

Теорема Евклида. Множество простых чисел бесконечно.

Доказательство.

Предположим противное, пусть p1,p2,...,pk все простые числа, где p1 = 2, а pk – самое большое простое число.

Составим натуральное число w = p1×p2 ×...×pк +1, т.к. w> pi , то оно должно быть составным, тогда его наименьший делитель будет простым (см. задачу 3). Однако w не делится ни на p1 , ни на p2 ,…, ни на pk , т.к. 1 не делится на любое pI.

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

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

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