Теорема Евклида – простых чисел бесконечно много.
Доказательство:
Предположим, что простых чисел не бесконечно много, а наоборот конечное число. Тогда их все можно обозначить буквами, например p1,p2,…,pn, в порядке возрастания. При этом n – количество всех простых чисел, а pn – наибольшее простое число. Очевидно, что p1 =2, p2=3, … .
Поскольку числами p1,p2, …,pn исчерпываются все простые числа, то все остальные числа являются составными. Значит все числа, больше pn, также составные. Как известно все составные числа можно разложить в произведение простых, т.е. произведение чисел p1*p2*…*pn.
А теперь надо найти число, которое больше pn, т.е. составное, и не делится ни на одно из чисел p1,р2,…,рn.
Т.е. M= p1,р2,…,рn+1. Это число M больше pn и, значит, составное. Поэтому оно должно делится на кокое-нибудь из чисел p1,р2,…,рn , но оно не делится ни на одно из чисел, т.к. даёт при делении остаток 1. Противоречие! С одной стороны, М – составное число, с другой стороны – не делится ни на одно простое число. Это противоречие показывает, что исходное предположение о конечности множества всех простых чисел неверно. Значит, простых чисел бесконечно много.
Из тетради:
Док. Пусть прост. Чисел конечное число, т.е. p1,р2,…,рn –все прост. числа.
Рассм. М= p1,р2,…,рn+1 ϵN
-
M – простое число (против., т.к. M>pi (i=1,2,…,n) либо
-
М – составное число => M:р, где р – простое=>M:рк (кϵ
