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

Примеры. Числа 2, 3, 5, 7, 11 простые, числа 4, 6, 18, 100 составные. Отметим, что число 1 не является ни простым, ни составным. Существует стандартная система обозначений простых чисел: Р 1 – первое по величине простое число (ясно, что Р 1 = 2), Р 2 – следующее простое число, (Р 2 = 3), (Р 3 = 5), (Р 4 = 7), (Р 5 = 11), (Р 6 = 13), (Р 7 = 17), (Р 8 = 19) и т.д. Вообще Р n – n-ое простое число. К сожалению, не существует аналитической формулы f (n), которая позволила бы вычислять любое простое число P n.

Теорема 2. Простых чисел существует бесконечно много. Доказательство. Допустим, существует лишь конечное число простых чисел. Перечислим их: P 1, Р 2, …, Р N. Значит, любое другое натуральное число содержит в качестве делителя по крайней мере одно из Р i (i = 1, 2, …, N). Рассмотрим число Р = Р 1 Р 2 … Р N + 1. Очевидно, что это число не делится ни на одно из чисел

так как при делении на любое из этих чисел Р дает в остатке 1. Значит, допущение о конечности множества простых чисел неверно. Простых чисел существует бесконечно много. Замечание. По дошедшим до нас историческим источникам это доказательство принадлежит Евклиду и является первым примером в математике доказательства «методом от противного». Простые числа являются «кирпичиками» из которых строятся все остальные натуральные и целые числа, отличные от 0, -1, 1.

Теорема 3. (основная теорема арифметики). Для любого натурального числа а 1 имеет место равенство а = для некоторых неотрицательных целых α 1, α 2, …, α к и натурального k. Правая часть равенства называется разложением числа а в произведение простых чисел. Такое разложение при фиксированной нумерации множества простых чисел единственно.

Пример. 10 = 2 5 = , 81 = 3 4 = , 200 = = 8 25 = =

Определение 4. Пусть а,b N. Число с называется общим делителем а и b, если оба они делятся на с без остатка. Примеры. Пусть а = 24, b = 36. Тогда общими делителями a и b будут числа 1, 2, 3, 4, 6 и 12. Число 8 не будет общим делителем чисел 24 и 36. Пусть а = 10, b = 30. Общие делители – 1, 2, 5. Пусть а = 16, b = 35. Общий делитель, равный 1, единственный.

Теорема 5. Пусть и Число b является делителем а в том и только в том случае, когда β i α i для любого i = 1,…, n.

Следствие 6. Пусть для натурального числа а имеет место равенство Тогда число делителей а вычисляется по формуле (α 1 + 1) (α 2 + 1) … (α n + 1).

Теорема 7. Пусть и Тогда число является общим делителем чисел а и b в том и только в том случае, когда γ 1 min (α 1, β 1 ), γ 2 min (α 2, β 2 ), …, γ n min (α n, β n ).

Определение 8. Число c называется наибольшим общим делителем чисел а и b (обозначение: с = НОД (а, b)), если с является самым большим из всех общих делителей чисел а и b. Примеры. Пусть а = 24, b = 30. Тогда НОД (24, 30) = 6. Если а = 10, b = 33, то НОД (10, 33) = 1; НОД (а, а) = а. Пусть а = 12, b = 48. Тогда НОД (12, 48) = 12.

Теорема 9. Пусть а и b натуральные числа, Тогда НОД (а,b)= где γ i = min (α i,β i ), i = 1,2,3, …, n.

Следствие 10. Любой общий делитель чисел а и b является также делителем НОД (а, b). Определение 11. Число а называется кратным числу b (а,b N), если а делится на b или, что тоже самое, b есть делитель а. Тот факт, что а делится на b, будет обозначать как b.

Пример. Пусть b =3. Тогда кратным ему будут числа 3,6, 9, 12, …. Их можно описать общей формулой а = 3n (n N). Этот пример показывает, что в отличие от делителей, количество кратных любому натуральному числу b бесконечно.

Определение 12. Если число а делится на число b и с, то а называется общим кратным чисел b и с. Примеры. Если b = 6, c = 8, то общее кратное этих чисел равно 24. Также общими кратными являются числа 48, 72, ….

Теорема 13. Пусть, Тогда число является общим кратным чисел b и с тогда и только тогда, когда α 1 max (β 1,γ 1 ), α 2 max (β 2,γ 2 ), …, α n max (β n,γ n ).

Доказательство. Пусть а – общее кратное b и с. Так как а делится на b, то α i β i, i = 1, 2, 3, …, n. Так как а делится на с, то α i γ i, i = 1, 2, 3, …, n. Так как α i β i и α i γ i, то α i max (β i,γ i ). Докажем в другую сторону. Так как α i max (β i,γ i ), то α i β i для каждого i = 1, 2, 3, …, n, значит а делится на b. Аналогично, а делится на с, то есть а – общее кратное b и с.

Определение 14. Самое маленькое из всех общих кратных натуральных чисел b и с называется наименьшим общим кратным b и с и обозначается НОК (b, c). Примеры. НОК (3, 5) = 15, НОК (4, 6) = 12, НОК (36, 64) = 576, НОК (2, 8) = 8, НОК (а, а) = а, НОК (1, а) = а.

Теорема 15. Пусть Число является НОК (b, с) в том и только в том случае, когда α i = max (β i,γ i ), i = 1, 2, 3, …, n

Следствие 16. Любое общее кратное чисел b и с делится на НОК(b, с). Лемма 17. Для любых чисел х, у max (x, y) + min (x, y) = x + y.

Доказательство. Рассмотрим три случая: 1) х = у, тогда max (x, y) = x, min (x, y) = x, поэтому max (x, y) + min (x, y) = 2 x и х + у = 2 х ; 2) х > у, тогда max (x, y) = x, min (x, y) = y, следовательно max (x, y) + min (x, y) = x + y ; 3) x < y, тогда max (x, y) = y, min (x, y) = x, поэтому max (x, y)+ min (x, y) = y + x = x + y.

Теорема 18. Для любых натуральных чисел b и с НОД (b, с) · НОК (b, с) = b · c. Доказательство. Пусть и Тогда

НОД(b,c)*НОК(b,c) = =

Определение 19. Числа а и b называются взаимно простыми, если НОД (а, b) = 1. Другими словами, если а и b не имеют общих делителей, отличных от 1. Примеры. 3, 8 – взаимно просты, 1, 5 взаимно просты, 4, 6 – не взаимно просты.

Определение 20. Функцией Эйлера φ (n) называется количество чисел меньших, либо равных n, которые взаимно просты с n. Примеры. 1) φ (12) = 4. Перечислим все числа 12 и взаимно простые с 12: 1,5, 7, 11; 2) φ(36) = 12. Перечислим все необходимые числа: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35; 3) φ(7) = 6.

Теорема 21. Пусть n =, причем α i > 0 и k i k j (i j), i,j= 1, 2, …, n. Тогда

Примеры. 1) n=56= , (56) = 56(1- )(1- ) = = 24; 2) n=16=2 4, (16) = 16(1- ) = 8; 3) (11) =11(1- ) = 10.