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

1⁰. Если р простое число, то

" а Î Z НОД(p, а) > 1 Û НОД(p, а) = p Û p | a.

Действительно, если D = НОД(p, а) > 1, то D Î {1, p} \ {1} = {p}, т.е. D = p. Остальные импликации очевидны.

Из свойства 1⁰ непосредственно вытекают следующие три свойства:

2⁰. Если р простое число, то " а Î Z НОД(p, а) = 1 Û p a.

3⁰. Если р и q – два простых числа, то НОД(p, q) > 1 Û p = q Û p | q.

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

5⁰. Простое число делит произведение двух целых чисел в том и только том случае, когда оно делит один из сомножителей.

Действительно, сформулированное утверждение эквивалентно (?!) следующему: простое число не делит произведение двух целых чисел в том и только том случае, когда оно не делит ни один из сомножителей. Для его доказательства используем доказанные ранее свойства простых и взаимно простых чисел:

p a×b Û (p, a×b)=1 Û ((p, a) = 1) Ù ((p, b) = 1) Û (p a) Ù (p b).

6⁰. Натуральное число п > 1 является простым тогда и только тогда, когда оно не делится ни на одно простое число 2 £ р £ .

Очевидно, что если n – простое, то оно не делится ни на одно простое число 2 £ р £ . Докажем обратное: если n не делится ни на одно простое число 2 £ р £ , то оно простое.

Это очевидно для n = 2. Рассуждая от противного, предположим, что доказываемое утверждение не верно для некоторого n > 2 и выберем наименьшее n с этим свойством. Тогда число n не простое, хотя и не делится ни на одно простое 2 £ р £ . Таким образом, n = n₁×n₂ для некоторых натуральных чисел п₁ , n₂ (1 < n₁ £ n₂ < n). При этом число п₁ не делится ни на одно простое число р £ , а тем более, ни на одно простое 2 £ р £ . Для n₁ доказываемое утверждение верно (т.к. n₁ < n), и значит, п₁ – простое число, на которое делится п . Поэтому п₁ > , однако это приводит к противоречию: п = n₁×n₂ ³ n₁² > ( )² = п .

Таким образом, предположение о том, что число п составное было неверным, и свойство 6⁰доказано.

Теорема (основная теорема арифметики). (1) Любое натуральное число n > 1 однозначно записывается в виде произведения: n = , где k Î N, a_i Î N, p₁ < … < p_k – простые числа.

(2) Любое целое число n, большее 1 по модулю, однозначно записывается в виде n = , где Î {–1, +1}, k Î N, _i Î N, p₁ < … < p_k – простые числа.

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

Доказательство. Прежде всего, (2) следует из (1): любое целое число n однозначно записавается в виде n = e×|n|, где знак e Î {–1, +1} совпадает со знаком числа n, причём в силу (1), |n| = .

(1) Докажем вначале существование канонического разложения. Если n – простое число, то n = n¹ – каноническое разложение числа n. Рассуждая от противного, предположим, что для некоторого n Î N, n > 1 не существует канонического разложения, и выберем наименьшее такое число n .

Ввиду предыдущих рассмотрений n > 1 не простое, значит, n – составное и n = n₁×n₂ для некоторых натуральных чисел n₁ , n₂ , больших 1, но меньших n. Поэтому у множителей n₁ и n₂ существуют канонические разложения: n₁ = , n₂ = , где a_i , b_j Î N₀и различным индексам соответствуют различные простые числа (при этом с нулевыми показателями степеней могут участвовать лишь общие для п₁ и п₂ простые числа р₁ , … , р_s). Тогда

n = ,

а каноническое разложение числа n получится, если в этом произведении переставить некоторые сомножители, упорядочив простые числа по возрастанию, и отбросить множители с нулевыми показателями степеней. Итак, существование канонического разложения доказано.

Примеры: 1. Найти каноническое разложение числа 11655.

Последовательно проверяем, делится ли данное число на простые числа p_i (2 £ p_i £ = 107,…), получая в случае деления частное n_i и сокращая верхнюю границу простых чисел до . Результат оформляем в виде таблички:

ni	11655	3885	1295	259	37	1
pi	3	3	5	7	37
	107,…	62,…	35,…	16,…	6,…	stop

Итак, 11655 = 3²×5¹×7¹×37¹.

2.Найти каноническое разложение числа 399.

ni	399	133	19	1
pi	3	7	19
	19,…	11,…	4,…	stop

Таким образом, 399 = 3×7×19.

3. Простое ли число 101 ?

Проверяем его делимость на простые из интервала 2 £ p £ » 10, … , т.е. на простые p = 2, 3, 5, 7. Ясно, 101 не делится на эти простые, а значит, само является простым числом.

С вычислительной точки зрения рассмотренный процесс разложения числа n в произведение простых очень трудоёмок: он сводится к перебору простых чисел, не превосходящих . Хотя есть более быстрые алгоритмы решения этой задачи, но принципиально эта трудность непреодолима – задача разложения числа на множители относится к классу так называемых NP-полных задач, для которых не найдено хороших алгоритмов решения. Например, существует 155-значное число, которое было разложено на множители только после семи месяцев интенсивных вычислений на самых современных компьютерах. Поэтому раскладывать в произведение, например, 1000-значные числа – почти всегда дело безнадёжное (разложите, тем не менее, число 10^1000000).

Следствие 1 (о делителях числа). Если a = ± – каноническое разложение целого числа a, то любой делитель d | a имеет вид d = ± , где 0 £ s_i £ a_i (1 £ i £ k).

Доказательство. Ясно, что любое число d = ± является делителем числа a = ± .

С другой стороны, если d | a и d = ± – каноническое разложение, то простые числа p_k+1 , … , p_m в этом разложении на самом деле отсутствуют, т.к. в противном случае должны были бы присутствовать и в каноническом разложении числа a. Значит, d = ± . При этом | a, а значит, 0 £ s_i £ a_i (1 £ i £ k).

Следствие 1 доказано.

Следствие 2 (о количестве натуральных делителей). Количество натуральных делителей целого числа a = ± равно

s(a) = (a₁ + 1)× … ×(a_k + 1).

Доказательство. Каждый натуральный делитель равен d = , где 0 £ s_i £ a_i (1 £ i £ k), и полностью определяется набором (s₁ ; … ; s_k). Таким образом, соответствие d = ® (s₁ ; … ; s_k) является взаимно однозначным, и остаётся только подсчитать количество всех таких наборов. Каждая i-япозиция такого набора может быть заполнена a_i + 1 способом, т.к. 0 £ s_i £ a_i .По принципу умножения получаем, что всего возможностей образования наборов равно (a₁ + 1)× … ×(a_k + 1).

Следствие 2 доказано.

Следствие 3 (о наибольшем общем делителе и наименьшем общем кратном). Для любых целых чисел a = ± , b = ± , где a_i , b_i Î NÈ {0}, p₁ < … < p_k – простые, имеют место равенства

НОД(a, b) = , где g_i = min{a_i , b_i},

НОК[a, b] = , где d_i = max{a_i , b_i}.

Доказательство. Ясно, что число D = ,где _i = min{a_i , b_i}, является общим делителем чисел a, b.С другой стороны, если число d – произвольный положительный общий делитель a и b , то по следствию 1 имеем d = , где 0 £ s_i £ a_i и 0 £ s_i £ b_i , т.е. 0 £ s_i £ g_i (1 £ i £ k). Следовательно, d D, и D – наибольший общий делитель чисел a, b.

Для наименьшего общего кратного имеем НОК[a, b] = = = , причём a_i + b_i – g_i = d_i для всех 1 £ i £ k. Последнее равенство очевидно: min{a, b} + max{a, b} – min{a, b} = = max{a, b}.

Следствие 2 доказано.

Упражнения: 1.Проанализируйте детально доказательства следствий и восполните все пробелы.

2. Выведите аналогичные формулы для НОД и НОК произвольного количества ненулевых целых чисел.

3. Чему равно количество общих натуральных делителей n чисел ? А целых ?

4. Чему равна сумма всех общих натуральных делителей n чисел ? А целых ?

Следствие 4 (о разложении степени на взаимно простые множители).Если произведение a₁×a₂× … ×a_k попарно взаимно простых натуральных чисел a₁ , … … , a_k является n-й степенью некоторого целого числа, то каждый сомножитель a_i является n-й степенью подходящего натурального числа.

Доказательство. Если sⁿ = a₁×a₂×…×a_k , то раскладывая в произведение простых множителей числа s, a₁ , … , a_n и замечая, что ввиду взаимной простоты, в разложениях a_i и a_j нет одинаковых простых (1 i < j k), получим, что любое простое число, входящее в разложение произвольного множителя a_i , имеет тот же показатель степени, что и в разложении для sⁿ. Таким образом, любое простое число в разложении каждого множителя участвует с показателем степени, делящимся на n, – т.е. каждый множитель является n-й степенью натурального числа.

Следствие 4 доказано.

Упражнения: 1. Справедливо ли следствие 4, если множители a_i (1 i k), предполагаются целыми, а не натуральными ?

2. Как нужно изменить формулировку, чтобы следствие 2 оставалось верным и для целых множителей ?