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

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

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

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

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

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

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

a = p₁p₂p₃…p_n.

Допустим, что для того же самого а существует и второе разложение на простые сомножители a = q₁q₂q₃…q_s. Тогда найдем

p₁p₂p₃…p_n = q₁q₂q₃…q_s.

Правая часть этого равенства делится на q₁. Следовательно (Теорема 2), по крайней мере один из сомножителей левой части должен делиться на q₁.

В разложении числа а на простые сомножители некоторые из них могут повторяться. Обозначая буквами p₁, p₂, …, p_k различные из них и буквами a₁, a₂,…, a_k кратности их вхождения в а, получим так называемое каноническое разложение числа а на сомножители

.

Пример: Каноническое разложение числа 588000 будет: 588000 = 2⁵?3?5³?7².

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

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

; 0 £ b₁ £ a₁, 0 £ b₂ £ a₂, …, 0 £ b_k £ a_k. (1)

Доказательство: Пусть d делит а.

Пример: Все делители числа 720 = 2⁴?3²?5 получим, если в выражении заставим b₁, b₂, b₃ независимо друг от друга пробегать значения b₁ = 0, 1, 3, 4; b₂ = 0, 1, 2; b₃ = 0, 1. Поэтому указанные делители будут 1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144, 5, 10, 20, 40, 80, 15, 30, 60, 120, 240, 45, 90, 180, 360, 720.

Теорема 5: Наибольший общий делитель нескольких чисел является произведением степеней вида p^a, где p – общий простой делитель всех этих чисел, а a - наименьший из показателей, с которыми p входит в их канонические разложения.

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

Доказательство: Пусть d - общий делитель чисел а, ..., l. Тогда имеют место равенства вида a = da₁, ..., l = dl₁, которые показывают, что: a) всякий простой делитель p числа d должен быть делителем и каждого из чисел а, ..., l, b) этот делитель p должен входить в каноническое разложение числа d с показателем, не превосходящим наименьшего из тех, с которыми он входит в канонические разложения чисел а, ..., l; обратно, каждое d, подчиненное условиям а) и b), очевидно, является общим делителем чисел а, ..., l.

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

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

Пример: Наибольший общий делитель чисел 6791400 = 2³?3²?5²?7³?11, 178500 = 2²?3?5³?7?17, 27720 = 2³?3²?5?7?11 равен 2²?3?5?7 = 420.

Теорема 7: Наименьшее общее кратное нескольких чисел является произведением степеней вида p^a, где p - простой делитель по меньшей мере одного из этих чисел, а a - наибольший из показателей, с которыми p входит в их канонические разложения.

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

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

Доказательство: Пусть М - общее кратное чисел a, ..., l. Тогда имеют место равенства вида М = ad', …, М = dl', которые показывают, что: a) всякий простой делитель p каждого из чисел а, ..., l должен быть делителем и числа М, b) этот делитель p должен входить в каноническое разложение числа М с показателем, не меньшим наибольшего из тех, с которыми он входит в канонические разложения чисел а, ..., l; обратно, каждое М, подчиненное условиям а) и b), очевидно, является общим кратным чисел а, ..., l.

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

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

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

Пример: Наименьшее общее кратное чисел 1800 = 2³?3²?5², 3780 = 2²?3³?5?7, 8910 = 2?3⁴?5?11 равно 2³?3⁴?5²?7?11 = 1247400. 6