§5. Простые числа и их свойства.

Определение 1. Натуральное число (р) называется простым, если р > 1 и не имеет положит. делителей, отличных от 1 и р.

Определение 2. Натуральное число а >1, имеющее кроме 1 и самого себя другие положительные делители, называется составным.

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

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

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

в) единица.

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

Задача 1. Доказать, что если aZ и р - простое число, то (а, р) = 1 v (a / р)

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

Пусть d = (а, р) => (a /d) & (р /d), т.к. р - простое число, то оно имеет два делителя 1 и р. Если (а, р) = 1, то а и р взаимно просты, если (а, р) = р, то (а/р).

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

Решение.

Пусть произведение (а₁,а₂,...,а_k)/р, если все a_i не будут делиться на р, тогда и произведение будет взаимно просто с р, следовательно, какой-то сомножитель делится на р.

Задача 3. Доказать, что наименьший отличный от 1 делитель целого числа а>1, есть число простое.

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

Пусть aZ и а - составное число (если а = р, то утверждение доказано), тогда а = a₁q.

Пусть q - наименьший делитель, покажем, что он будет простым числом. Если предположить, что q - составное число, тогда q = q₁k и а = a₁•q₁k, т.к. q₁<q, то q - уже не будет наименьшим делителем, что противоречит условию задачи. Следовательно, q - простое число.

Задача 4. Доказать, что наименьший простой делитель (р) натурального числа (n) не превосходит n .

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

Пусть n = рn₁, причем р < n₁ и р - простое. Тогда n  р² => р<n .

Из этого утверждения следует, что если натуральное число (n) не делится ни на одно простое число р n , то n – простое, в противном случае оно будет составным.

Пример 1. Выяснить, будет ли число 137 простым? 11 <137 <12.

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

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

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

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

Составим натуральное число  = p₁p₂ ...p_к +1, т.к.  p_i , то оно должно быть составным, тогда его наименьший делитель будет простым (см. задачу 3). Однако  не делится ни на p₁ , ни на p₂ ,…, ни на p_k , т.к. 1 не делится на любое p_I.

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

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

Теорема об интервалах. В натуральном ряду существует сколь угодно длинные интервалы, не содержащие ни одного простого числа.

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

Возьмём произвольное натуральное число (n) и составим последовательность натуральных чисел (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1).

В этой последовательности каждое последующее число на 1 больше предыдущего, все эти числа составные, т.к. каждое имеет более двух делителей (например, первое число делится на 1, на 2 и само на себя). При n→∞ мы получим сколь угодно длинный интервал, состоящий только из составных чисел.

Теорема Евклида и теорема об интервалах свидетельствуют о сложном характере распределения простых чисел в натуральном ряду.

Основная теорема арифметики

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

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

Докажем возможность представления:

Пусть nN и n>1, если n – простое число, то n = p и теорема доказана. Если n – составное, то наименьший его делитель будет числом простым и n = p₁n₁, где n₁<n.

Далее рассуждаем аналогично. Если n₁ простое число, то теорема доказана, если n₁ составное число, то n₁ = p₂n₂ , где n₂ < n₁ и тогда n = p₁p₂n₂ . На каком-то шаге получим n = p₁p₂ …p_n , где все p_i - простые числа.

Докажем единственность разложения:

Предположим, что для числа (n) есть два различных представления: n = p₁p₂ …p_k, n = q₁q₂ …q_n и n>k.

Тогда получим, что p₁p₂ …p_k = q₁q₂ …q_n (1). Левая часть равенства (1) делится на p₁, тогда по свойству простых чисел (см. задача 2), по крайней мере, один из сомножителей правой части должен делиться на p₁.

Пусть (q₁/p₁) => (q₁=p₁). Разделив обе части равенства (1) на p₁, получим равенство p₂p₃ …p_k = q₂q₃ …q_n . Повторяя прежнее рассуждение ещё (k-1) раз, мы получим равенство 1 = q_k+1q_k+2 …q_n , т.к. все q_i >1, то это равенство невозможно. Следовательно, в обеих разложениях число сомножителей одинаково (k=n) и сами сомножители одинаковы.

Замечание. В разложении числа (n) на простые сомножители некоторые из них могут повторяться. Обозначая буквами ₁,₂,…,_k кратность их вхождения в (n), получим так называемое каноническое разложение числа (n):

Пример 2.

Каноническое разложение числа 588000 = 2⁵35³7²

Следствие 1. Если тогда все делители числа (n) имеют вид: где 0_i_i (i = 1, 2,…,k).

Пример 3. Все делители числа 720 = 2⁴3²5 получим, если в выражении вместо₁, ₂, ₃ , независимо друг от друга, будем подставлять значения: ₁=0, 1, 2, 3, 4, ₂=0, 1, 2, ₃ = 0, 1.

Искомые делители будут равны: 1; 2; 4; 8; 16; 3; 6; 12; 24; 48; 9; 18; 36; 72; 144; 5; 10; 20; 40; 80; 15; 30; 60; 120; 240; 45; 90; 180; 360; 720.

Следствие 2. Если и то (a, b) = p₁^1 p₂^2 …p_k^k, где i = min(_I, _i)

[a, b] = p₁^1 p₂^2 …p_k^k , где i = max(_I, _i).

Пример 4. Найти НОД(a, b) и НОК(a, b), используя каноническое разложение, если

a = 24, b = 42.

(24, 42) = 23 = 6

[24, 42] = 2³37 = 168