Основная теорема арифметики

Если то всё доказано. Если то по свойству 2, по свойствам взаимно простых чисел ▲.

Замечание: использовано следующее свойство взаимно простых чисел:

Доказательство:

▲.

Следствие: Если произведение нескольких чисел делится на простое число р, то хотя бы один из сомножителей делится на это число р. (доказательство методом математической индукции по числу п сомножителей).

Теорема 1. (ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ). Всякое натуральное число, большее 1, может быть представлено в виде произведения простых сомножителей и два таких разложения могут отличаться только порядком следования сомножителей.

Доказательство: 1. Возможность указанного представления. Применим метод математической индукции.

1) Для числа 2 утверждение теоремы тривиально.

2) Допустим, что теорема верна для всех натуральных чисел, меньших п.

3) Докажем теорему для числа п. Если п — простое число, то всё доказано.

Если п — составное число, то Тогда в силу индуктивного предположения допускают разложение на простые множители:

Тогда и возможность разложения числа п доказана.

2. Однозначность разложения. Для доказательства однозначности разложения с точностью до порядка следования сомножителей также применим метод математической индукции.

1) Для числа 2 утверждение справедливо, т. к. 2 – простое число.

2) Допустим, что утверждение верно для всех натуральных чисел, меньших п.

3) Докажем утверждение для числа п. Допустим, что п двумя способами разложено в произведение простых сомножителей: и , где простые числа .

Тогда один из сомножителей произведения делится на .

Тогда Но число Тогда по индуктивному предположению для т утверждение справедливо, т. е. два разложения числа т могут отличаться только порядком следования сомножителей. Следовательно, простые числа только порядком следования. Значит утверждение верно и для числа п.

Итак, по методу математической индукции утверждение верно для любого натурального числа, большего 1. ▲.

Замечание: Среди сомножителей в разложении могут быть равные. Их произведение принято записывать в виде степеней. Пусть различные простые сомножители числа п и число входит в разложение числа п раз , тогда число п можно записать в виде: . Такое разложение называется каноническим разложением числа п.

Пример: Найдем каноническое разложение числа 1176.

Значит

Применения основной теоремы арифметики

Если у нас есть канонические разложения двух натуральных чисел, то мы можем считать, что эти разложения состоят из одинаковых простых сомножителей, добавляя сомножители вида .

Например, Считают, что

Теорема 2. Пусть канонические разложения натуральных чисел п и т. Тогда где

где

Примеры: 1.

2. Пусть . Найдем их канонические разложения: