§ 5. Единственность разложения на простые сомножители

a. Всякое целое а или взаимно просто с данным простым , или же делится на .

Действительно, , будучи делителем , может быть равно или 1, или . В первом случае а взаимно просто с , во втором а делится на .

b. Если произведение нескольких сомножителей делится на данное простое , то, по крайней мере, один из сомножителей делится на .

Действительно (а), каждый сомножитель или взаимно прост с , или же делится на . Если бы все сомножители были взаимно просты с , то и их произведение (3, f, § 2) было бы взаимно просто с . Поэтому хоть один сомножитель делится на .

c. Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом (если отвлечься от порядка следования сомножителей).

Действительно, пусть а — целое, большее 1; обозначая буквою его наименьший простой делитель, имеем . Если то, обозначая буквою его наименьший простой делитель, имеем . Если , то подобно этому находим и т.д., пока не придем к какому-либо равному 1. Тогда получим Перемножив все найденные равенства и произведя сокращение, получим следующее разложение а на простые сомножители:

Допустим, что для того же самого а существует и второе разложение на простые сомножители . Тогда найдем

Правая часть этого равенства делится на Следовательно (b), по крайней мере один из сомножителей левой части должен делиться на Пусть, например, делится на (порядок следования сомножителей в нашем распоряжении); тогда найдем кроме 1 делится только на Сократив обе части равенства на получим

Повторив прежние рассуждения применительно к этому равенству, получим пока, наконец, в одной части равенства, например, в левой не сократятся все сомножители. Но одновременно должны сократиться и все сомножители правой части, так как равенство при превосходящих 1, невозможно. Таким образом, второе разложение на простые сомножители тождественно первому.

d. В разложении числа а на простые сомножители некоторые из них могут повторяться. Обозначая буквами различные из них и буквами кратности их вхождения в а, получим так называемое каноническое разложение числа а на сомножители

Пример. Каноническое разложение числа 588 000 будет:

e. В заключение мы докажем несколько теорем, касающихся делителей числа, а также общего наибольшего делителя и общего наименьшего кратного нескольких чисел.

1. Пусть - каноническое разложение числа а. Тогда все делители числа суть все числа вида

Действительно, пусть d делит с. Тогда и, следовательно, все простые делители числа d входят в каноническое разложение числа а с показателями, не меньшими тех, с которыми они входят в каноническое разложение числа d. Поэтому d имеет вид (1).

Обратно, всякое d вида (1) делит а.

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

2. Общий наибольший делитель нескольких чисел является произведением степеней вида где — общий простой делитель всех этих чисел, а а — наименьший из показателей, с которыми входит в их канонические разложения.

3. Совокупность общих делителей нескольких чисел совпадает с совокупностью делителей их общего наибольшего делителя.

Действительно, пусть - общий делитель чисел Тогда имеют место равенства вида которые показывают, что: а) всякий простой делитель числа d должен быть делителем и каждого из чисел , а также что: b) этот делитель должен входить в каноническое разложение числа d с показателем, не превосходящим наименьшего из тех, с которыми он входит в канонические разложения чисел а, обратно, каждое d, подчиненное условиям а) и b), очевидно, является общим делителем чисел

Общим наибольшим делителем, т. е. наибольшим из общих делителей (а, § 2) является тот из последних, в каноническом разложении которого показатели степеней простых чисел точно равны наименьшим из тех, с какими эти простые числа входят в канонические разложения чисел .

А всякий общий делитель, как имеющий в своем каноническом разложении все показатели не превосходящими соответствующих показателей в каноническом разложении общего наибольшего делителя, будет делителем последнего.

Пример. Общий наибольший делитель чисел равен

4. Общее наименьшее кратное нескольких чисел является произведением степеней вида , где — простой делитель по меньшей мере одного из этих чисел, а — наибольший из показателей, с которыми входит в их канонические разложения.

5. Общее наименьшее кратное нескольких попарно простых чисел равно их произведению.

6. Совокупность общих кратных нескольких чисел совпадает с совокупностью кратных их общего наименьшего кратного.

Действительно, пусть М — общее кратное чисел а,

Тогда имеют место равенства вида которые показывают, что: а) всякий простой делитель каждого из чисел должен быть делителем и числа М, а также что: b) этот делитель должен входить в каноническое разложение числа М с показателем, не меньшим наибольшего из тех, с которыми он входит в канонические разложения чисел а, обратно, каждое М, подчиненное условиям а) и b), очевидно, является общим кратным чисел а, l.

Общим наименьшим кратным, т. е. наименьшим из общих кратных ( § 3), является то из последних, в каноническом разложении которого показатели степеней простых чисел точно равны наибольшим из тех, с какими эти простые числа входят в канонические разложения чисел .

В случае, когда - попарно простые и, следовательно, каждый множитель вида канонического разложения общего наименьшего кратного входит в каноническое разложение одного и только одного из чисел общее наименьшее кратное последних, очевидно, равно их произведению.

Всякое общее кратное, как имеющее в своем каноническом разложении все показатели не меньшими соответствующих показателей в каноническом разложении общего наименьшего кратного, будет кратным последнего.

Пример. Общее наименьшее кратное чисел равно .