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