Изменения

Перейти к: навигация, поиск

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

78 байт добавлено, 17:19, 28 января 2017
м
Нет описания правки
{{Определение
|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> называется '''простым''', если <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>.
}}
# Простые числа.
# Составные числа.
# Число <tex>1</tex>, которые которое не причисляется ни к простым, ни к составным числам.
{{Утверждение
|about=свойство 1|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>.
{{Утверждение
|about=свойство 2|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>q</tex> не наименьшее число в множестве <tex>M</tex>. Получили противоречие. Значит <tex>q</tex> простое число.
}}
По утверждению Из свойства <tex>2</tex> мы получаем алгоритм для поиска простых чисел "[[Решето Эратосфена]]".
==Множество простых чисел==
Пусть множество простых чисел конечно и состоит из чисел <tex>2,3,5, \dots p</tex>, где <tex>p</tex> {{---}} последнее, самое большое простое число.
Рассмотрим число <tex>N=2*3*5* \dots *p +1</tex>. Число <tex>N</tex> не делится на все простые числа (<tex>2, 3, 5, \dots , p</tex>), так как при делении <tex>N</tex> на эти числа получится остаток <tex>1</tex>.
Значит число <tex>N=1</tex> (по утв. свойству <tex>2</tex>), так как у числа <tex>N</tex> нет простых делителей по предположению.C другой стороны <tex>N>1</tex>. Значит предположение, что множество простых чисел конечно , неверно.
}}

Навигация