344
правки
Изменения
м
Поправлена пунктуация
{{Определение
|definition=
[[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|Натуральное]] число <tex>p</tex> называется '''простым''' (англ. ''prime number''), если <tex>p>1</tex> и <tex>p</tex> не имеет натуральных [[Классы_чисел#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5|делителей]] , отличных от <tex>1</tex> и <tex>p</tex>.
}}
{{Определение
|definition=
[[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|Натуральное]] число <tex>n>1</tex> называется '''составным''' (англ. ''composite number''), если <tex>n</tex> имеет по крайней мере один натуральный [[Классы_чисел#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5|делитель]] , отличный от <tex>1</tex> и <tex>n</tex>.
}}
|statement=Если <tex>p_1</tex>, <tex>p_2</tex> {{---}} различные простые числа, то <tex>p_2</tex> '''не [[Натуральные_и_целые_числа#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.87.D0.B8.D1.81.D0.B5.D0.BB_.D1.81_.D0.BE.D1.81.D1.82.D0.B0.D1.82.D0.BA.D0.BE.D0.BC|делится без остатка]]''' на <tex>p_1</tex>.
|proof=
Натуральными делителями простого числа <tex>p_2</tex> являются только <tex>1</tex> и <tex>p_2</tex>. Простое число <tex>p_1 \neq 1</tex> , и <tex>p_1 \neq p_2</tex>. Значит <tex>p_2</tex> не делится на <tex>p_1</tex>.
}}
|statement=Для любого [[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|натурального]] числа <tex>n>1</tex>, наименьший отличный от <tex>1</tex> натуральный делитель всегда является '''простым числом'''.
|proof=
Рассмотрим множество <tex>M</tex>, состоящее из натуральных, отличных от <tex>1</tex> , делителей числа <tex>n</tex>. Множество <tex>M</tex> не пустое, так как <tex>n \in M</tex>. Значит , в множестве <tex>M</tex> существует наименьшее число <tex>q>1</tex>.
Пусть <tex>q</tex> не простое, тогда существует <tex>a</tex> такое, что <tex>1<a<q</tex> и <tex>q</tex> делится на <tex>a</tex>. Так как <tex>n</tex> делится на <tex>q</tex>, то <tex> n</tex> делится на <tex>a</tex>. (Так как <tex>n</tex> делится на <tex>q</tex>, то существует такое натуральное число <tex>k</tex>, что <tex>n = k\,q</tex>. Так как <tex>q</tex> делится на <tex>a</tex>, то существует такое натуральное число <tex>f</tex>, что <tex>q = f\,a</tex>. Следовательно, существуют такие натуральные числа <tex>f</tex>, <tex>k</tex>, что <tex>q = k\,f\,a</tex>, т.е. <tex> n</tex> делится на <tex>a</tex>.) Значит , <tex>q</tex> не наименьшее число в множестве <tex>M</tex>. Получили противоречие. Значит , <tex>q</tex> — простое число.
}}
Из свойства <tex>2</tex> мы получаем алгоритм для поиска простых чисел "[[Решето Эратосфена]]".
==Множество простых чисел==
Пусть множество простых чисел конечно и состоит из чисел <tex>2, 3, 5, \ldots , p</tex>, где <tex>p</tex> {{---}} последнее, самое большое простое число.
Рассмотрим число <tex>N=2 \times 3 \times 5 \times \ldots \times p +1</tex>. Число <tex>N</tex> не делится ни на одно из простых чисел (<tex>2, 3, 5, \ldots , p),</tex>), так как при делении <tex>N</tex> на эти числа получится остаток <tex>1</tex>.
Значит , число <tex>N=1</tex> (по свойству <tex>2</tex>), так как у числа <tex>N</tex> нет простых делителей по предположению.C другой стороны , <tex>N>1</tex>. Значит , предположениео том, что множество простых чисел конечно, неверно.
}}
