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

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

Натуральное число [math]p[/math] называется простым, если [math]p\gt 1[/math] и [math]p[/math] не имеет положительных делителей отличных от [math]1[/math] и [math]p[/math]

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

Натуральное число [math]n\gt 1[/math] называется составным, если [math]n[/math] имеет по крайней мере один положительный делитель отличный от [math]1[/math] и [math]n[/math].

Свойства простых чисел

Утверждение (1):

[math]p_1[/math], [math]p_2[/math] — различные простые числа, то [math]p_1[/math] не делится без остатка на [math]p_2[/math].

[math]\triangleright[/math]

Положительными делителями простого числа [math]p_2[/math] являются только [math]1[/math] и [math]p_2[/math]. Простое число [math]p_1 \neq 1[/math] и [math]p_1 \neq p_2[/math]. Значит [math]p_1[/math] не делится на [math]p_2[/math]

[math]\triangleleft[/math]

Утверждение (2):

Для любого натурального числа [math]n\gt 1[/math], наименьший, отличный от [math]1[/math] положительный делитель всегда является простым числом

[math]\triangleright[/math]

Рассмотрим множество [math]M[/math] — положительные, отличные от [math]1[/math] делители числа [math]n[/math]. Множество M не пусто, так как [math]n \in M[/math]. Значит в множестве [math]M[/math] существует наименьшее число [math]q\gt 1[/math]. Пусть [math]q[/math] не простое, тогда существует [math]a[/math] такое, что [math]1\lt a\lt q[/math] и [math]q[/math] делится на [math]a[/math]. Так как [math]n[/math] делится на [math]q[/math], то [math] n[/math] делится на [math]a[/math]. Значит [math]q[/math] не наименьшее число в множестве [math]M[/math]. Получили противоречие. Значит [math]q[/math] простое число.

[math]\triangleleft[/math]

По этой теореме мы получаем алгоритм для поиска простых чисел "Решето Эратосфена".

Множество простых чисел

Утверждение:

Множество простых чисел бесконечно

[math]\triangleright[/math]

Пусть множество простых чисел конечно и состоит из чисел [math]2,3,5, \dots p[/math], где [math]p[/math] — последнее, самое большое простое число. Рассмотрим число [math]N=2*3*5* \dots *p +1[/math]. Число [math]N[/math] не делится на числа [math]2, 3, \dots , p[/math]. Так как при делении [math]N[/math] на эти числа получится остаток [math]1[/math]. Значит число [math]N=1[/math] (по утв. [math]2[/math]). C другой стороны [math]N\gt 1[/math]. Значит предположение, что множество простых чисел конечно неверно.

[math]\triangleleft[/math]

Последовательность простых чисел начинается так:

[math]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, \dots [/math]

См. также

• Натуральные и целые числа
• Основная теорема арифметики
• Теоремы о простых числах
• Разложение на множители (факторизация)

Источники инфомации

• А.А. Бухштаб. "Теория чисел" — Просвещение. 1966 г. — с. 28 - 33.
• И. М. Виноградов. "Основы теории чисел" — c. 18 - 20.