При
разложении
на простые
множители
числа n
удобно
объединять
одинаковые
сомножители,
запиывая их
в виде
степеней.
Так как
любое число
натуральное
число
можно
записать в
виде
где
- простые
числа,
,
.
В этой
записи можно
было бы
считать, что
(то есть
),
однако
удобно
разрешать и
.
Тогда
некоторые
сомножители
равны
и
соответствующее
число
в разложении
(7) фактически
отсутствует.
Благодаря
этому мы
можем любые
два числа
записать в
виде:
с одними и
теми же
простыми
,
...,
.
Здесь
,
-
неотрицательные
целые числа.
Теорема 6.
Если
и
записаны в
виде (8), то
где
означает
наименьшее
из двух
чисел
и
.
Доказательство. Если , то разложение на простые множители по теореме единственности есть часть разложения (если , то разложение можно получить, перемножая разложения и ). Поэтому , где . Если к тому же , то , откуда . НОД получается при . Теорема доказана.
Пример. Рассмотрим числа и . Имеем: , . Отсюда .
Определение. Наименьшим общим кратным (НОК) двух отличных от целых чисел и называется наименьшее число , для которого и . НОК чисел и мы будем обозначать через .
Теорема 7.
Пусть
натуральные
числа
и
записаны в
виде (8). Тогда:
где
означает
наибольшее
из двух
чисел
,
.
Доказательство аналогично доказательству предыдущей теоремы.
Пример. .
Следствие 1. .
В самом деле, .
Следствие 2. Если и , то .
Теорема 8 (Евклид). Простых чисел бесконечно много.