Наибольший общий делитель

Введем понятия общего делителя, наибольшего общего делителя. Число d Є Z делящее одновременно числа я_1ля₂, ...,а_к Є Z назовем общим делителем этих чисел. Наибольшее число с таким свойством называется наибольшим общим делителем чисел

Обозначение:d =НОД{а₁, а₂, ...,а.Д)-

Очевидно, что если d = НОД(а₁₎а₂,... .аД), то число (—с?)также является наибольшим по абсолютной величине общим делителем чисел СХ1, ••• f •

Далее будем рассматривать только положительное значение НОД(ЯрЯ₂, ...,а_п

Теорема 2.4

Если а кратно Ь, то совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного Ь; в частности (я, Ь) = Ь.

Доказательство. Всякий общий делитель чисел я и ^является делителем и одного Ь. Обратно, раз я кратно Ъ, то всякий делитель числа b является также делителем числа я, т. е. является общим делителем чисел b и а. Таким образом, совокупность общих делителей чисел я и ^совпадает с совокупностью делителей одного Ь. А так как наибольший делитель числа Ьесть само Ь, то НОД(я, Z?) = Ь.

Ч.т.д.

Если НОД (а₁,а₂,..., a_n) = 1, то числаа₁,а₂,...,а_п называются взаимно простыми.

Если каждое из чисел а, Ь, ...,1 взаимно просто с каждым другим из них, то а,Ь, ...,/ называются попарно простыми. Очевидно, числа попарно простые всегда и взаимно простые. Например, числа 8, 13, 21 - попарно простые, так как (8, 13) =1, (8, 21) = 1, (13, 21) = 1, а, следовательно, и взаимно простые.

Обратно же, в общем случае, неверно.

Например, числа 6, 10, 15 взаимно простые, так как

НОД (6, 10, 15)= 1.

При этом не одна из пар этих чисел не является взаимно простой.

Действительно, НОД (6, 10)=2, НОД(6,15)=3, НОД(Ю,15)=5.

Теорема 2.5

Если каждое а_х, а₂,..., а_т взаимно просто с каждым b₁,b₂,...,b_n, то и произведение а₁а₂,..., а_т взаимно просто с произведением Ь₁Ь₂,..., Ь_п.

Доказательство. Находим

(а.^, а₂а₃ ... а_т, Ь]Д — (cz.2^3 O-m> ^k) ~ (^3 ••• ^m> ^k) ~ !• (2.7)

Обозначим a_lt a₂a₃ ... a_m = A,

тогда

(Ь-Д^.-.Д^А) = ДД₃,...,Ь_п,А) = (b₃,...,b_n,A) = ... = (b_n,A) = 1. (2.8)

НОД ...,б/и=НОД (d_n_₁,a_n).

Число сообщим делителем чисел а_г, ...,а_п.

Ч.т.д.

Теорема 2.6

Пусть т - любое положительное целое, тогда

(ат, Ьт) = (а, Ь)т (2.9)

Теорема 2.7

Частные от деления двух чисел на их наибольший общий делитель -числа взаимно простые.

Доказательство. Умножив соотношения почленно на т, получим новые соотношения, где вместо а, Ь,т, ..., г_п будут ат, Ьт, тт, ...,г_пт. Поэтому (ат, Ьт) = г_пт и, таким образом, верно утверждение теоремы.

Ч.т.д.

Теорема 2.8

Если (а, Ь) = 1,то (ас, Ь) = (Ь,с).

Доказательство, (ас, Ь) делит ас и Ьс, значит, оно делит и (ас, Ьс) равное с. Но (ас, Ь) делит и Ь, поэтому оно делит и (с, Ь).

Обратно, (с, Ь) делит ас и Ь, поэтому оно делит и (ас, Ь).

Таким образом, (ас, Ь) и (с, Ь) взаимно делят друг друга и, следовательно, равны между собой.

Ч.т.д.

Теорема 2.9

Если (а, Ь) = 1 и ас делится на Ь, то с делится на Ь.

Доказательство. При ас, делящемся на Ь, имеем

(ас, b) = Ь

и получаем Ь = (с, Ь), что означает делимость с на Ь.

Ч.т.д.

Теорема 2.10

Если а = bq + с, то совокупность общих делителей чисел а и Ь совпадает с совокупностью общих делителей чисел Ь и с; в частности

(а, Ь) = Д, с).

Доказательство. Равенство

(а, Ь) = (Ь, с) показывает, что всякий общий делитель чисел а и Ьделит также с и, следовательно, является общим делителем чисел Ь и с.

Верно и обратное, то есть равенство

(а, Ь) = (Ь, с) показывает, что всякий общий делитель чисел b и с делит а и, следовательно, является общим делителем чисел а и Ь. Таким образом, общие делители чисел а и b те же, что и общие делители чисел b и с.

В частности, должны совпадать и наибольшие из этих делителей, т. е. НОД(а, h)= НОД(Ь, с).

Ч.т.д.