wpthemepostegraund

Пункт 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 1 + bv 1 ) – ( au 2 + bv 2 ) q = a ( u 1 u 2 q )+ b ( v 1 v 2 q ) Î P .

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

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

¨

Свойство 2 . Для любых целых чисел а и 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 . Тогда:

( а / s , b / s ) =

( a , b )


s

.

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

( a , b ) =

æ
ç
è

a


s

s ,

b


s

s

ö
÷
ø

= s

æ
ç
è

a


s

,

b


s

ö
÷
ø

. ¨

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

æ
ç
è

a


( a , b )

,

b


( a , b )

ö
÷
ø

= 1.

Свойство 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) совпадают. Есть ли у Васи шанс?


Thanks: Ruliz