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

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

Теорема 2. Простых чисел существует бесконечно много.
Доказательство. Допустим, существует лишь

так как при делении на любое из этих чисел Р дает

Теорема3. (основная теорема арифметики). Для любого натурального числа а ≠ 1

Пример.
10 = 2 ∙ 5 = 21 ∙ 30

Определение 4. Пусть а,b N. Число с называется общим делителем а

Теорема 5. Пусть 
и 
Число b является делителем а в том и только

Следствие 6.
Пусть для натурального числа а имеет место равенство
Тогда число

Теорема 7. Пусть
и
Тогда число
является общим делителем чисел а

Определение 8.
Число c называется наибольшим общим делителем чисел а и

Теорема 9. Пусть а и b натуральные числа,
Тогда НОД (а,b)=

Следствие 10.
Любой общий делитель чисел а и b является также

Пример. Пусть b =3.
Тогда кратным ему будут числа 3,6, 9,

Определение 12.
Если число а делится на число b и с,

Теорема 13. Пусть,
Тогда число
является общим кратным чисел b и с

Доказательство.
Пусть а – общее кратное b и с.

Определение 14.
Самое маленькое из всех общих кратных натуральных чисел b

Теорема 15. Пусть
Число
является НОК (b, с) в том и

Следствие 16.
Любое общее кратное чисел b и с делится на

Доказательство. Рассмотрим три случая:
1)       х = у, тогда
max (x, y)

Теорема 18.
Для любых натуральных чисел b и с
НОД (b,

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

Определение 19. Числа а и b называются взаимно простыми, если НОД

Определение 20.
Функцией Эйлера φ (n) называется количество чисел меньших, либо

Теорема 21.
Пусть
n = ,
причем αi > 0 и