1.2. Наибольший общий делитель н наименьшее общее кратное
Определение 1.6. Целое число d≠0 называется наибольший общим делителем целых чисел а1, а2, . ак (обозначается d = НОД(а1, а2, . ak)), если выполняются следующие условия:
каждое из чисел а1, a2. ak делится на d;
если d1≠ 0 — другой общий делитель чисел а1, а2. ak, то d делится на d1
Ненулевые целые числа а и b называются ассоциированными (обозначается а
b), если а делится на b и b делится на а.
Теорема 1.2 (об ассоциированных числах). Числа а и b ассоциированы тогда и только тогда, когда а = ±b.
Доказательство. Пусть а делится на b, тогда существует такое целое число с, что а=bс. Поскольку |c| ≥ 1, получаем |a|= |b|*|c|≥|b|*1=|b|, то есть |a|≥|b|
В то же время b делится на а. Проводя аналогичные выкладки, получаем |b|≥ |а|. Таким образом, |a| = |b|, то есть а = ±b.
Теорема 1.3 (о единственности наибольшего общего делителя). Пусть числа a1, а2, . ak целые и d1—их наибольший общий делитель. Целое число d2 является наибольшим общим делителем чисел а1, а2,. аk тогда и только тогда, когда d2
d1.
Доказательство. Число d1 — наибольший общий делитель чисел a1, a2… ak, а d2 — общий делитель этих чисел. Значит, по определению наибольшего общего делителя, d1 делится на d2. Точно так же, если рассматривать d2 как наибольший общий делитель чисел a1, a2,…ak, a d1— как общий делитель этих чисел, то d2 делится на d1. Таким образом, d1
d2. Необходимость доказана.
Теперь докажем достаточность. Пусть d2
d1. Тогда, по определению наибольшего общего делителя, каждое из чисел а1, а2,. ak делится на d1. Кроме того, числа d1 и d2 ассоциированы, поэтому d1 делится на d2. Значит, каждое из чисел а1, a2, . ak делится на d2. Таким образом, d2 — общий делитель чисел а1, а2, . ak. Покажем теперь, что он наибольший.
Пусть δ — некоторый общий делитель чисел а1, а2,. ak. По условию d1 = НОД(a1, а2 …ak) , тогда d1 делится на δ. А раз d2
d1, то d2 делится на d1, значит d2 делится на δ и d2 = НОД(a1, а2, …ak).
Учитывая теоремы 1.2, 1.3, далее для определенности наибольший общий делитель целых чисел будем считать положительным числом.
Теорема 1.4 (о существовании и линейном представлении наибольшего общего делителя). Для любых целых чисел а1, а2, . ak существует наибольший общий делитель d, и его можно представить в виде линейной комбинации этих чисел: d= c1a1 + c2a2 + . + ckak, где сi Z.
Доказательство [I]. Пусть A = — множество всевозможных целочисленных линейных комбинаций чисел а1, а2,. аk. Будем считать, что не вес числа а1, а2,… аk нулевые, тогда в множестве А существует наименьший положительный элемент. Обозначим его d. Покажем, что множество А совпадает с множеством всех целых чисел, кратных d. Поскольку число d может быть представлено в виде линейной комбинации чисел а1, а2, . ak то и любое число вида xid где x Z, может быть представлено в виде линейной комбинации этих чисел.
Обратно, любая линейная комбинация чисел а1, а2 …аk делится на d. Действительно, применим к числу d и произвольному элементу у А теорему о делении с остатком: существуют такие целые числа q и r, что y=qd+ r, причем 0≤r<d. Число r=y — qd является элементом множества А. поскольку у Аи d А. Но d — наименьший неотрицательный элемент множества А, значит, r = 0 и y=qd. Таким образом, A=.
Осталось доказать, что d — это наибольший общий делитель чисел a1, а2…ak. Каждое из этих чисел имеет вид xid, где х Z (достаточно рассмотреть линейную комбинацию вида 0*a1 + 0*a2 + … + 0 * ai-1 + 1*аi, + 0 *ai+1 +… + 0 * аk). Таким образом, d — общий делитель чисел а1, а2,. ak.
Пусть с — любой другой делитель этих чисел. Тогда по свойству 2 делимости с делит каждую линейную комбинацию вида с1а1 + c2a2 + . + ckak, в том числе и ту, которая равна d. □
Определение 1.7. Целые числа а1, a2, . ак называются взаимно простыми в совокупности, если НОД(а1, а2,. аk) = 1. Целые числа а и b называются взаимно простыми, если НОД(а, b)=1.
Определение 1.8. Целые числа а1 а2, . ak называются попарно взаимно простыми, если НОД(ai, аj)= 1 для всех 1 ≤ i≠j ≤ k.
Взаимно простые числа обладают следующими свойствами.
Для того чтобы целые числа а1, а2, . ak были взаимно простыми в совокупности, необходимо и достаточно, чтобы существовали такие целые числа с1, с2,…сk, что c1a1 + c2a2 + . + сkаk = 1
Доказательство. Необходимость следует из теоремы о существовании и линейном представлении наибольшего общего делителя. Докажем достаточность. Пусть целые числа с1,c2…сk таковы, что c1a1 + c2a2 + . + сkаk = 1 и пусть d= НОД(a1 ,a2,…, ak). Тогда, по определению наибольшего общего делителя, каждое из чисел а1, а2, . ак делится на d. Значит, по свойству 2 делимости, и сумма c1a1 + c2a2 + . + сkаk делится на d, то есть 1 делится на d, следовательно, по свойству 6 делимости, d = 1. Таким образом, 1 = НОД(a1, а2,. аk) и числа ai взаимно просты в совокупности.
1’. Для того чтобы целые числа а, b были взаимно простыми, необходимо и достаточно, чтобы существовали такие целые числа m, п, что та + nb = 1.
Пусть произведение ab делится на с и НОД(а, с) = 1. Тогда b делится на с.
Доказательство. Числа а и с взаимно просты, тогда, по свойству 1’, существуют такие целые числа т, n, что та + пс =1. Домножим обе части последнего равенства на b:
mab + ncb = b.
Первое слагаемое в левой части равенства делится на с по условию. Второе слагаемое, очевидно, делится на с. Значит, и b делится на с.
3. Если НОД(а, b) = 1, НОД(а, с) = 1, то НОД(a, bс) = 1.
Доказательство. Числа а и b взаимно просты, поэтому по свойству 1' число 1 можно представить в виде 1 = та + пb, где числа т и n целые. Умножим обе части этого равенства на с, получим
с = mac + nbc.
Пусть d — наибольший общий делитель чисел а и bc. Тогда оба слагаемых в правой части равенства делятся на d, а значит и число с делится на d. Но 1 — наибольший общий делитель чисел а и с, то есть 1 делится на d и d= 1. □
Если НОД( a , b 1)=1, НОД( а , b 2 )=1, . НОД( а , b k )=1, то
НОД(а,b1b2..bk)= 1.
Пусть целые числа а1, а2, . аl, b1, b2, . bk таковы, что НОД(аi,bj)=1 для всех 1≤ i≤ l, 1≤ j≤ k. Тогда НОД(a1a2..al,b1,b2. bk)=1.
Пусть целое число а делится на b1 и на b2, НОД(b1 b2) = 1. Тогда a делится на произведение b1b2.
Доказательство. Число а делится на b1 поэтому существует такое целое число с, что a = cb1.
Так как а делится на b2. то произведение cb1 делится на b2 Но поскольку НОД(b1 b2) = 1, значит, по свойству 2 взаимно простых чисел, с делится на b2, то есть существует такое целое число d. что с = db2. Отсюда а = cb1 = db1b2, то есть а делится на b1b2, □
Если а делится на каждое из попарно взаимно простых чисел b1, b2. bk, то а делится на произведение b1b2. bk.
Определение 1.9. Целое число М называется наименьшим общим кратным целых чисел а1, а2,…,аk, аi≠0 для i=1, 2, . k (обозначается М=НОК(a1, а2, . ak)), если выполняются следующие условия:
М делится на каждое из чисел а1,а2, . ak;
если Mt — другое общее кратное чисел a1, а2. ak, то Mt делится на М.
Наибольший общий делитель и наименьшее общее кратное двух положительных целых чисел связаны соотношением:
НОД(а, b) • НОК(а, b) = аb.