Не затягивая развития событий, начнем сразу с определения.
Определение. Число 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 , очевидно, справедливо: ( а , 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ы не спускаются в забой - боятся, что там бабай. Многолетняя работа ученых Уральского отделения Академии Наук увенчалась успехом. Ими создан уникальный прибор - анализатор смысла проделанной работы. Вчера верховный шаман Судана Пантелеймон-ибн-Иван-Иван-ибн был застигнут гражданами за странным занятием - он брил своего бегемота, хотя тому нет еще и четырнадцати. Неслыханная наглость! Недавно студент-первокурсник Семочкин пришел на экзамен по матанализу со своим эпсилон! Иван Иванович шел по улице, упал в яму и орал, пока не вылез. Сегодня и ежедневно в Доме Культуры работников Мясокомбината демонстрируется художественный фильм "Молчание ягнят". |