Глухов М. М. Алгебра том 1, страница 13

Так как О < тд < Ь, то О < т < Ь, и для чисел о, т условия (1) — (2) выполнены. в) а — любое, Ь < О. Тогда по доказанному в пунктах а) и б) найдутся такие числа од,тд, что Таким образом, существование неполного частного и остатка доказано во всех случаях. Докажем единственность. Допустим, что для целых чисел а, Ь, д, т, од, тд выполняются соотношения (1) — (2) и соотношения: Тогда имеем Ьд+ т = Ьдд + тд, и потому Так как т, тд — неотрицательные числа, меньшие !Ь|, то !тд — т! < !Ь!. Однако при о ф од из последнего равенства и утверждения 1 б) следует, что !тд — т! > !Ь!. Значит, о = од, а тогда и т = тд.

П Ниже остаток от деления а на Ь будем обозначать через ть(а). Сравнивая определение 15.111 отношения делимости и определение 1 деления с остатком и учитывая единственность неполного частного и остатка, получим С л е д с т в и е. Если а, Ь Е Ж и Ь ф О, шо Ь ! а <=» ть(а) = О.

8 2. Наибольший общий делитель и наименьшее общее кратное целых чисел О п р е д е л е н и е 2. Наибольшим общим делишелем (НОД) чисел ад,...,а„Е Ж, называют любое целое число д, удовлетворяющее 4~ условиям: а) с~ есть общий делитель чисел ад,..., а„, т. е. с~ ~ ад,...,д ~ а„; б) д делится на любой общий делитель чисел ад,..., а„, т.

е. Жд Е У: (ад ~ ад,...,4 ~ а„=» дд ~ Й). Множество всех наибольших общих делителей чисел ад,..., а„, обозначим через НОД (ад,..., а„). Ниже мы докажем, что множество НОД (ад,..., а„) не пусто при любых ад,..., а„Е Ж. Пока же установим лишь более слабое У т в е р ж д е н и е 2. Если ад = = а„= О, то для чисел ад,..., а„, существует единственный НОД, равный О. Если целые числа ад,...,а„, не все равны 0 и для них существует хопдя бы один НОД, то они имеют ровно два НОД, которые отличаются только знаком. П При ад = = а„= 0 число а = 0 удовлетворяет условиям определения 2, а число Й ф 0 удовлетворяет условию а) и не удовлетворяет условию б), поскольку, например, д+ 1 ~ О, но д+ 1 ~ д. Следовательно, НОД (О,...,0) = (0).

Пусть теперь целые числа ад,..., а„, не все равны О, и д Е НОД (ад,...,а„), т. е. д удовлетворяет условиям определения 2. Тогда 4 ф О, и из утверждения 1 а) следует, что этим условиям удовлетворяет также число — а. Если целое число 4 также является НОД чисел ад,...,а„, то по условию б) определения 2 дд ~ д и д ~ дд, а тогда по утверждении 1 в) имеем ~дд~ = ~д~, т. е.

дд = й или 4 = — д. Таким образом, в рассматриваемом случае НОД (ад,..., а„) = ( — й, а). П Из утверждения 2 следует, что если множество НОД (ад,...,а„) не пусто, то в нем содержится единственное неотрицательное число. Условимся обозначать его через (ад,...,а„). Для решения вопроса о существовании НОД чисел ад,..., а„ограничимся сначала рассмотрением случая п = 2.

В этом случае для нахождения НОД существует известный алгоритм, описанный на геометрическом языке Евклидом г. Пусть даны два целых числа а, Ь. Если Ь = О, то, очевидно, НОД (а, Ь) Э а. Поэтому будем считать, что Ь ф О. г Евклид — древнегреческий математик (365 — 300 лет до н. э.), впервые осуществивший систематизацию и аксиоматическое изложение накопившихся геометрических знаний. Алгорипдм Евклида для целых чисел а, Ь при условии Ь ф 0 заключается в следующем. Сначала делим с остатком а на Ь: а = Ьвд + тд, 0 < тд < ~Ь!. Если тд — — О, то алгоритм окончен. В этом случае Ь ~ а, и, очевидно, Ь Е НОД(а,Ь). Если же тд ф О, то делим с остатком Ь на тд .

Ь = = тддг+ тг, 0 < тг < тд. Если тг = О, то алгоритм окончен, в противном случае делим с остатком тд на тг и т. д. до тех пор, пока не получим остаток, равный нулю. Такой момент обязательно наступит, поскольку получающиеся остатки являются целыми неотрицательными числами и образуют строго убываюшую цепочку тд > тг > .... Если остатки тд,..., т„отличны от нуля, а т„+д —— О, то имеем следующую систему соотношений: а=Ьвд+тд, О<тд < ~Ь|, Ь = тдвг + тг, 0 < тг < ~тд~, тд = тгдз + тз, 0 < тз < 1тг1, (3) т г=т дд +т, 0<т <~т тп-д = тпЧп+д Прослеживая систему равенств из (3) снизу вверх, нетрудно заметить последовательно, что т„делит числа т„д, т„г,..., тд, Ь, а. Следовательно, т„есть общий делитель чисел а, Ь.

Если дд какой-либо другой их общий делитель, то, прослеживая систему равенств (4) сверху вниз, получим последовательно: ад делит тд, тг,...,т„. Следовательно, т„= (а, Ь). Отсюда, с учетом утверждения 2, можно сделать вывод о том, что справедлива Т е о р е м а 2. Для любых целых чисел а, Ь сущесшвуеш единственный неотрицательный наибольший общий делитель (а, Ь). При этом, если а ~ Ь или Ь ~ а, то соответственно (а, Ь) = а или (а, Ь) = Ь, в противном случае (а, Ь) совпадает с последним не равным нулю остапдком в алгорипдме Евклида для чисел а, Ь. Т е о р е м а 3. Для любого натурального числа и > 2 и любых целых чисел ад,..., а„существует НОД, причем единственный неотрицательный НОД чисел ад,..., а„находится по формуле: (ад,..., а„) = Ц...

((ад, аг), аз),..., а„д), а„). 68 69 прит+1=2: аи+ Ьи = д. (4) сс2 = (сс1 %с+1) сс1 = (а1 а2 ° ° ° ~Ис). Таблица 4 Т1, = аи1, + Ьи1,, Й Е 1, п, (5) и начальными условиями: (7) ио = О, и1 = 1, ио = 1 и1 = — Ч1 а1и1 +... + а„и„= д. (9) а1и1+ + а„и„= 1. 71 70 П Докажем это утверждение индукцией по и. При и = 2 оно следует, из теоремы 2.

Допустим, что оно верно для п = й > 2 и докажем его для п = й+ 1. По теореме 2 сс1 — (( ° ° ((а1 а2) а3) ° ° ° ) Юс) сс2 — (( ° ° ((а1 а2) аз) ° ° ° ) %с+1) являются вполне определенными числами из Хо, и для доказательства теоремы достаточно показать, что а2 Е НОД (а1,..., а1-., а1-.» 1). Из определения чисел а1, а2 и из предположения индукции получаем равенства: Пользуясь равенствами (4), нетрудно проверить, что д2 удовлетворяет обоим условиям определения НОД чисел а1,..., а1,, а1,+1.

Проверьте это самостоятельно. П Используя алгоритм Евклида, нетрудно представить любой НОД чисел а1,..., а,„в виде целочисленной линейной комбинации этих чисел. Сделаем это сначала для т = 2. Т е о р е м а 4. Если т1,...,т„,Ч1,...,ׄ— последовательности осташков и неполных частных в алгоритме Евклида для чисел а,Ь, шо выполняются равенства: где и1,, и1, — целые числа, определяемые рекурреншными соотношениями: ии = иа — 2 — иа — 1Ф, ик = и1 -2 — иа-19 (6) П Сначала заметим, что числа и1,..., и„, и1,..., ип однозначно определяются условиями (6), (7). Теперь индукцией по й докажем, что они удовлетворяют соотношениям (5). При й = 1 равенство (5) имеет вид т1 = а — ЬЧ1 и легко получается из 1-й строки системы (3). Допустим, что соотношение (5) выполняется для й Е 1, т, где 1 < т < п, и докажем его для й = т+ 1. Из т+1-го равенства системы соотношений (3), используя предположение индукции, получим при т+ 1 > 2: Ттп» 1 = Ттп 1 — ТтпЧтп»-1 = (аитп-1 + Ьитп-1) (аитп + Ьитп)Чтп+1 = = а(итп 1 — итпЧтп+1) + Ь(итп — 1 итпЧтп+1) = аитп+1 + ~йтп+11 т2 = Ь вЂ” т1 Ч2 = Ь вЂ” (аи1+ Ьи1)Ч2 — — а( — и1Ч2)+ + Ь(1 и1Ч2) = а(ио и1Ч2) + Ь(ио и1Ч2) = аи2 + Ьи2.

С л е д с т в и е. Если а, Ь е У и д = (а, Ь), шо существуют такие целые числа и, и, чшо выполняется равенство: П Если д = а или д = Ь, то утверждение очевидно. Если д ф а, д ф Ь, то по теореме 2 й = т„, и искомыми целыми числами и, и могут служить числа и„, ип из равенства (5) при й = п. ПрОцЕСС ВЫЧИСЛЕНИЯ ЧИСЕЛ щ, иаэс ИЗ (5) И, В ЧаСтНОСтИ, ЧИСЕЛ и, и ИЗ (8) удобно проводить с помощью следующей таблицы. П Используя теорему 3 и следствие теоремы 4, нетрудно индукцией по и доказать Утвержден не 3. Пусть а1,...,а„Е У,и > 2. Если(а1,...,а„) = = а, шо существуют такие целые числа и1,...,и„, чшо Заметим, что обратное утверждение в общем случае неверно. Приведите соответствующий пример.

О п р е д е л е н и е 3. Целые числа а1,..., а„называются взаимно простыми (в совокупности), если (а1,..., а„) = 1. У т в е р ж д е н и е 4. Целые числа а1,..., а„взаимно просты тогда и только тогда, когда сУЩесшвУюш и1,..., ип Е Ж такие, чшо П Если (а1,..., а„) = 1, то нужные числа и1,..., и„существуют по утверждению 3. Обратно, если при некоторых и1,..., и„выполняется равенство (9) и д [ а1,..., д [ а„, то д [ 1.

Следовательно, (а1,..., а„) = =1.П Приведем наиболее часто используемые свойства взаимно простых чисел. Т е о р е м а 5. Для любых целых чисел а, Ь, с, справедливы утверждения: а) (а,Ь) = 1,(а,с) = 1 ~ (а,Ьс) = 1; б) а ) Ьс, (а, Ь) = 1 =~ а ) с; в) а [ с, Ь [ с, (а, Ь) = 1 ~ аЬ [ с; г) (а,Ь) = с,с ф О ~ (а/с,Ь/с) = 1. П а) Из условия и утверждения 4 следует существование целых чисел и1, и1, иг, иг, удовлетворяющих равенствам: аи1 + Ьи1 = 1, аиг + сиг = 1. Перемножив эти равенства почленно, получим: аи + (Ьс)и = 1, где и = аи|иг + Ьи1иг + си1иг, и = и1иг.

Отсюда по утверждению 4 имеем (а, Ьс) = 1. б) По условию при подходящих о, и, и Е Ж выполняются равенства: Ьс = ао, аи+ Ьи = 1. Умножив последнее равенство на с и заменив после этого Ьс на ао, получим а(си)+а(ци) = с и а(си+ди) = с. Следовательно, а[с. в) Как и в случае б), имеем равенства: с = ад1, с = Ьдг, аи + Ьи = 1, (ц1, ог, и, и е У,). Умножив последнее равенство на с и учитывая два предыдущих равенства, получим: аЬцги+ аЬц1и = с. Отсюда видно, что аЬ ~ с. г) Из условия и утверждения 3 следует, что с [ а, с [ Ь и существуют целые числа и, и, удовлетворяющие равенству аи + Ьи = с. Отсюда имеем а Ь а Ь вЂ” и + -и = 1, т. е.

—, — = 1. П с с * с с О п р е д е л е н и е 4. Наименьшим общим кратным (НОК) целых чисел а1,..., а„при и > 2 называется любое целое число й, удовлетворяющее условиям: а) Й есть общее кратное чисел а1,..., а„, т. е. а1 [ Й,..., а„[ Й; б) й делит любое общее кратное чисел а1,..., а„, т. е. ЧЙ1 Е У(а1 [ Й1,..., а„] Й1 — — ~ Й [ Й1). Множество всех НОК чисел а1,..., а„обозначим через НОК (а1,... ..., а„).