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

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

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

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

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

Согласно определениям, множество натуральных чисел разбивается на [math]3[/math] подмножества:

1. Простые числа.
2. Составные числа.
3. Число [math]1[/math], которое не причисляется ни к простым, ни к составным числам.

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

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

Если [math]p_1[/math], [math]p_2[/math] — различные простые числа, то [math]p_2[/math] не делится без остатка на [math]p_1[/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_2[/math] не делится на [math]p_1[/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]. Множество [math]M[/math] не пустое, так как [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]n[/math] делится на [math]q[/math], то существует такое натуральное число [math]k[/math], что [math]n = k\,q[/math]. Так как [math]q[/math] делится на [math]a[/math], то существует такое натуральное число [math]f[/math], что [math]q = f\,a[/math]. Следовательно, существуют такие натуральные числа [math]f[/math], [math]k[/math], что [math]q = k\,f\,a[/math], т.е. [math] n[/math] делится на [math]a[/math].) Значит, [math]q[/math] не наименьшее число в множестве [math]M[/math]. Получили противоречие. Значит, [math]q[/math] — простое число.

[math]\triangleleft[/math]

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

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

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

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

[math]\triangleright[/math]

Пусть множество простых чисел конечно и состоит из чисел [math]2, 3, 5, \ldots , p[/math], где [math]p[/math] — последнее, самое большое простое число. Рассмотрим число [math]N=2 \times 3 \times 5 \times \ldots \times p +1[/math]. Число [math]N[/math] представимо в виде [math]N=2 \times (3 \times 5 \times \ldots \times p) +1,[/math] где [math]2\,[/math] — делитель, [math](3 \times 5 \times \ldots \times p)\,[/math] — частное, [math]1\,[/math] — остаток, причем [math]0\leqslant 1 \lt 2.[/math] Таким образом, при делении [math]N[/math] на [math]2[/math] получится остаток [math]1[/math], число [math]N[/math] на простое число [math]1[/math] не делится. Аналогично [math]N[/math] не делится ни на одно из простых чисел ([math]3, 5, \ldots , p),[/math] так как при делении [math]N[/math] на эти числа получится остаток [math]1[/math]. Значит, число [math]N=1[/math] (по свойству 2), так как у числа [math]N[/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, \ldots [/math]

См. также

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

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

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