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

NS НОВОСТИ

Всего один раз помянул старое адмирал Нельсон.

Новость из Кузбасса. Уже втоpую неделю кузбасские шахтеpы не спускаются в забой - боятся, что там бабай.

Многолетняя работа ученых Уральского отделения Академии Наук увенчалась успехом. Ими создан уникальный прибор - анализатор смысла проделанной работы.

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

Неслыханная наглость! Недавно студент-первокурсник Семочкин пришел на экзамен по матанализу со своим эпсилон!

Иван Иванович шел по улице, упал в яму и орал, пока не вылез.

Сегодня и ежедневно в Доме Культуры работников Мясокомбината демонстрируется художественный фильм "Молчание ягнят".