§ 1. Основные понятия и теоремы

Пункт 2. Наибольший общий делитель.

Не затягивая развития событий, начнем сразу с определения.

Определение. Число d О Z , делящее одновременно числа а , b , c , ... , k О Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , b , c , ..., k ) .

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

Теорема (Свойство 1) . Если ( a , b ) = d , то найдутся такие целые числа u и v , что d = au + bv .

Доказательство . Рассмотрим множество P = { au + bv з u,v О Z }. Очевидно, что P Н Z , а знатоки алгебры могут проверить, что P – идеал в Z . Очевидно, что a , b , 0 О P . Пусть x , y О P и y № 0 . Тогда остаток от деления x на y принадлежит P . Действительно:

x = yq + r , 0 Ј r < y ,

r = x – yq = ( au ₁ + bv ₁ ) – ( au ₂ + bv ₂ ) q = a ( u ₁ – u ₂ q )+ b ( v ₁ – v ₂ q ) О P .

Пусть d О P - наименьшее положительное число из P (призадумайтесь, почему такое имеется!). Тогда а делится на d . В самом деле, a = dq + r ₁ , 0 Ј r ₁ < d , a О P , d О P , значит r ₁ О P , следовательно r ₁ = 0. Аналогичными рассуждениями получается, что b делится на d , значит d - общий делитель a и b .

Далее, раз d О P , то d = au ₀ + bv ₀ . Если теперь d ₁ - общий делитель a и b , то d ₁ | ( au ₀ + bv ₀ ), т.е. d ₁ | d . Значит d і d ₁ и d - наибольший общий делитель.

Ё

Свойство 2 . Для любых целых чисел а и k , очевидно, справедливо: ( а , kа ) = а ; (1, а ) = 1.

Свойство 3 . Если a = bq + c , то совокупность общих делителей a и b совпадает с совокупностью общих делителей b и с , в частности,

( a , b ) = ( b , c ).

Доказательство. Пусть d | a , d | b , тогда d | c . Пусть d | c , d | b , тогда d | a .

Ё

Конечно, я привел здесь это "крутое" доказательство не потому, что читатели не смогли бы его придумать самостоятельно, а потому, что мне хочется, опять-таки, проиллюстрировать это доказательство на древнегреческий лад. Посмотрите на рис. 2:

Рис. 2

Если d целое число раз укладывается в а и в b , то, очевидно, что d обязано целое число раз уложиться и в с . Наглядная иллюстрация! Спасибо грекам.

Свойство 4 . Пусть a , b и m - произвольные целые числа. Тогда

( am , bm ) = m ( a , b ).

Доказательство. Если d - наибольший общий делитель чисел а и b , то dm | am и dm | bm , т.е. dm - делитель am и bm . Покажем, что dm - наибольший общий делитель этих чисел. Поскольку d - наибольший общий делитель чисел а и b , то, согласно свойству 1, для некоторых целых чисел u и v выполнено равенство d = au + bv . Умножив это равенство на m , получим равенство:

dm = amu + bmv .

Видно, что если некоторое число s делит одновременно am и bm , то s обязано делить и dm , т.е. s Ј dm , следовательно, dm - наибольший общий делитель.

Ё

Свойство 5 . Пусть s - делитель а и b . Тогда:

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

Свойство 6 . Очевидно теперь, что

Свойство 7 . Если ( a , b ) = 1, то ( ac , b ) = ( c , b ).

Доказательство . Пусть ( c, b ) = d . Имеем: d | b , d | c , следовательно d | ac , т.е. d - делитель ас и b . Пусть теперь ( ac , b ) = s . Имеем: s | b , s | ac , s - делитель b , т.е. либо s = 1, либо s не делит а . Это означает, что s | c , значит s | d . Итак, d и s делятся друг на друга, т.е. d = s .

Ё

Что еще сказать в этом пункте? Да, пожалуй, больше и нечего.

Задачки

1 . Докажите, пожалуйста, что если d = ( a 1 , a 2 , ... a n ) - наибольший общий делитель чисел a 1 , a 2 , ... a n , то найдутся такие целые числа v 1 , v 2 , ... v n , что d = v 1 a 1 + v 2 a 2 +...+ v n a n ). 2 . Вася любит Машу. Маша тоже любит Васю, но согласна выйти за него замуж только если наибольшие общие делители у пар чисел (2 3 ·5·13·45, 5 23 ·11 6 ·21) и (6·35·10, 17 4 ·15·55) совпадают. Есть ли у Васи шанс?