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

Определение 9.1.Натуральное число p называется простым, если оно имеет только два различных между собой натуральных делителя: 1и p.

Примеры.2, 3, 5, 7, 11, 13– простые числа.

Определение 9. 2. Натуральное число, большее единицы, называется составным, если оно имеет более двух различных натуральных делителей.

Примеры.4, 6, 8, 9, 10, 12 – составные числа.

Замечание 1.Из этих определений следует, что множество натуральных чисел можно разбить на три класса:

а) составные числа;

б) простые числа;

в) единица.

Если а – составное, то а = nq, где 1 < n < a, 1 < q < a.

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

1⁰. Если а Z и p – простое, то (а, p) = 1 а p.

Действительно, пусть d = (a, p), тогда (а d) p d, т.к. p – простое число, то оно имеет два делителя 1 и p. Если (а, p) = 1, то а и p взаимно просты, а если (а, p) = p, то а p.

2⁰. Если произведение нескольких сомножителей делится на p, то, по крайней мере, один из сомножителей делится на p.

Действительно, пусть произведение а₁ ∙ а₂ ∙ … ∙ а_n делится на p. Если предположить противное: все а_i не делятся на p, то (а₁ ∙ а₂ ∙ … ∙ а_n, p) = 1, следовательно, какой-то сомножитель делится на p.

3⁰. Различные простые числа взаимно просты.

4⁰. Наименьший простой делитель p натурального числа n > 1 не превосходит .

Пусть n = p ∙ n₁, причем p n₁ и p – простое. Тогда n p² p .

5⁰. Если натуральное число n не делится ни на одно простое число p , то n – простое, в противном случае оно будет составным.

Данное свойство непосредственно следует из свойства 4⁰.

Пример. Выясним, будет ли число 157 простым?

Выпишем простые делители, не превосходящие : 2, 3, 5, 7, 11. Проверяем, что 157 не делится на 2, на 3, на 5, на 7, на 11. Следовательно, число 157 – простое.

Решето Эратосфена

На свойстве 5⁰ основан метод, позволяющий определить список простых чисел p₁ < p₂ < … до заданной границы n. Этот метод носит название решето Эратосфена, названный в честь древнегреческого математика, географа и астронома.

Шаг 1. Выпишем подряд все натуральные числа 2, … , n – 1, n.

Положим, что p₁ = 2 и вычеркнем все последующие числа, делящиеся на 2, кроме p₁ = 2.

Шаг 2. Пусть k 2 и уже определены числа p₁,…, p_k-1. Обозначим p_k первое невычеркнутое число, следующее за p_k-1. Если p_k² > n, то обозначим p_k+1, p_k+2, … все оставшиеся невычеркнутыми числа, следующие за p_k, в порядке возрастания. На этом алгоритм завершает свою работу.

Шаг 3. Если p_k² n, то вычеркиваем числа, делящиеся на p_k, начиная с p_k² (двигаясь до n с шагом p_k). Вычеркнутые ранее числа также принимаются в учет, но не вычеркиваются еще раз. По завершении процедуры алгоритм увеличивает индекс k на единицу и переходит к шагу 2.

В результате алгоритм оставляет невычеркнутыми только простые числа.

Примеры: 1.Найти все простые числа, меньшие 30.

Применим решето Эратосфена, остановившись, как только найдём простое число, не меньшее = 5,…, т.е. простое число 7.

Теорема Евклида. Основная теорема арифметики

Теорема 9.1 (теорема Евклида). Множество простых чисел бесконечно.

Доказательство.

Предположим противное, пусть p₁, p₂, … , p_k – все простые числа, где p₁ = 2, а p_k – самое большое простое число.

Составим натуральное число n = p₁ · p₂ · … · p_k + 1, т.к. n > p_i, то оно должно быть составным. Покажем, что наименьший делитель q 1 числа n будет простым. Так как n – составное, то n = n₁ ∙ q, где q < n₁. Если предположить, что q – составное число, то q = q₁ ∙ k и n = n₁ ∙ q₁ ∙ k, так как q₁ < q, то q – уже не будет наименьшим делителем числа n, что противоречит условию. Итак, наименьший делитель числа n будет простым. Однако n не делится ни на p₁, ни на p₂, … , ни на p_k, так как 1 не делится на любое p_i .

Следовательно, наше предположение о конечности множества простых чисел было неверно.

Замечание 2. Простые числа составляют лишь небольшую часть чисел натурального ряда. Доказано, что в натуральном ряду существуют сколь угодно длинные интервалы, не содержащие ни одного простого числа.

Теорема 9. 2 (основная теорема арифметики). Любое натуральное число n > 1 может быть представлено единственным образом в виде произведения простых чисел, с точностью до порядка сомножителей.

Доказательство.

I. Докажем возможность представления методом математической индукции по величине числа. Пусть n N и n > 1.

1) n = 2. Утверждение выполняется, так как 2 – простое число.

2) Предположим, что утверждение теоремы выполнено для всех натуральных чисел,меньших числа k.

3) Покажем, что утверждение выполнено для k.

а) Если k – простое число, то доказывать нечего.

б) Если k – составное число, то оно имеет делитель а, такой, что 1 < a < k . Тогда k = a ∙ b. Очевидно, что 1 < b < k. Согласно предположению, теорема выполнена для чисел а и b, т. е. а = p₁ ∙ p₂ ∙ … ∙ p_s и b = q₁ ∙ q₂ ∙ … ∙ q_m, где p_i, q_j – простые. Тогда k = p₁ ∙ p₂ ∙ … ∙ p_s ∙ q₁ ∙ q₂ ∙ … ∙ q_m. Полученная формула означает, что существует представление числа k в виде произведения простых чисел.

Согласно принципа математической индукции возможность представления в виде произведения простых чисел доказана для любого натурального n > 1.

II. Покажем, что представление числа n в виде произведения простых чисел единственно с точностью до порядка сомножителей.

Пусть n = p₁ ∙ p₂ ∙ … ∙ p_s и n = q₁ ∙ q₂ ∙ … ∙ q_r, где p_i, q_j – простые числа, тогда будет иметь место равенство:

p₁ ∙( p₂ ∙ … ∙ p_s) = q₁ ∙ q₂ ∙ … ∙ q_r (1)

Тогда простое число p₁ делит q₁ ∙ q₂ ∙ … ∙ q_r, так что p₁ делит одно из простых чисел правой части, пусть q₁ p₁ , а значит, p₁ = q₁ . Поэтому обе части рассмат­ри­ва­е­мого равенства можно сок­ра­тить на p₁. Разделив обе части равенства (1) на p₁, получим равенство p₂ ∙ … ∙ p_s = q₂ ∙ … ∙ q_r . Повторяя процесс рассуждения еще (s – 1) раз, мы получим равенство:

1 = q_s+1 ∙ q_s+2 ∙ …∙ q_r

Так как все q_i > 1, то это равенство невозможно. Следовательно, в обеих разложениях число сомножителей одинаково (s = r) и сами сомножители одинаковы.

Замечание 3. В разложении числа n на простые сомножители некоторые из них могут повторяться. Обозначим буквами кратность их вхождения в n, получим так называемое каноническое разложение числа n: