Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
Выберем теперь в множестве M наименьшее положительное число d. Покажем, что а и b делятся на d. Пусть т\ — остаток пРи делении а на d. Так как and принадлежат М, то, в силу только дао сказанного, гх принадлежит Af. Но 0 ^ rx < d, a d — наименьшее положительное число, содержащееся в М. Следова-
10
ЦЕЛЫЕ ЧИСЛА
[ГЛ. I
ТеЛЬНО, Г\ НЄ МОЖеТ бЫТЬ ПОЛОЖИТеЛЬНЫМ ЧИСЛОМ, TaK ЧТО Г\ = 0.
Это значит, что а делится на d. Те же соображения приводят к выводу, что Ь делится на d. Таким образом, d есть общий делитель а и Ь. Далее, так как deM, существуют целые и0 и и0 такие», что d = auo + bv0. Пусть теперь d' — какой-либо общий делитель для а и Ь. Из равенства d = аы0 + bv0 заключаем, что d делится на d', ибо оба слагаемых правой части равенства делятся на d'. Поэтому d ^ d!, так что d есть наибольший общий делитель. По ходу рассуждения оказались доказанными оба утверждения теоремы.
4. Алгорифм Евклида. Метод доказательства теоремы 2 очень быстро приводит к цели, но он не дает средства для фактического вычисления d. Предлагаемый способ — найти наименьшее натуральное число в бесконечном множестве чисел M — совершенно не эффективен. Однако деление с остатком позволяет быстро «спускаться» внутри M к наименьшему натуральному числу, содержащемуся в М, т. е. к наибольшему общему делителю. Именно, поделим с остатком а на b (считаем, что ЬФО), затем b на первый остаток, затем первый на второй и т. д. Получим цепочку равенств и неравенств:
a. = bqi + ri, 0 < n s^l&l— Ь b = ri<H2 + r2, 0 < r2 ^ r\ — 1 и т. д.
Каждый последующий остаток есть натуральное число, строго меньшее предыдущего. Поэтому процесс не может продолжаться без конца. Но закончиться он может только на том, что на каком-то шагу деление выполнится без остатка.' Таким образом,
fl = ty, + г„ 0<г,<|й|-1;
b = rxq2 + r2, 0<r2<ri—1;
г\ = гд3 + г3, 0<r3<r2—1;
Гк-2 = гк_Лк +rk, 0 < rft</v.,—1;
Покажем, что последний отличный от нуля остаток г* равен н.о. д. (а, Ь). Для этого сначала пересмотрим все равенства снизу вверх: Гк-і делится на rk, rk~2, как сумма двух чисел, делящихся на г*, тоже делится на rk и т. д. К третьему сверху равенству мы придем, зная, что г2 и г3 делятся на rk, и заключим отсюда, что г\ делится на rk. Из второго заключим, что b делится на г-,, из первого — что а делится на rk. Таким образом, а и Ь делятся на rk.
Пусть теперь d' — какой-либо общий делитель для а и Ь. Пересмотрим равенства сверху вниз с точки зрения делимости на d!'. Из первого равенства заключаем, что г\ как разность двух чисел, делящихся на d', делится на d', Из второго — что г2 делится на й' по той же причине, и т. д. Из предпоследнего заключим, что
ТЕОРИЯ ДЕЛИМОСТИ ЦЕЛЫХ ЧИСЕЛ
И
гк делится на а" и, следовательно, rk ^ d'. Итак, г* оказывается общим делителем, причем наибольшим.
Изложенный способ отыскания н.о. д. называется алгорифмом Евклида, он известен уже более 2 000 лет. В процессе доказательства мы вновь установили свойство (2) н. о. д. Далее, из сказанного ранее ясно, что все остатки r\, г 2, ¦ ¦ ¦, Tk принадлежат множеству М, что дает доказательство и свойства (1), причем представление остатков в виде au + bv легко осуществляется шаг за шагом. Таким образом, алгорифм Евклида дает не только способ вычисления н.о.д. чисел а и ft, но и его линейное представление в виде аио + bv0.
Пример. Пусть а = 959, ? = 343. Найти их н.о.д. и найти его линейное представление.
Решение: 959 = 343-2 + 273; 343 = 273-1 + 70; 273 = = 70-3 + 63; 70 = 63-1 +7; 63 = 7-9 + 0. Таким образом, d = 7. Далее, 273 = 959 — 343-2; 70 = 343-273-1 = 343-(959 —
— 343-2)-1 =343-3 — 959; 63 = 273 — 70-3 = 959 — 343-2 —
— (343-3-959)-3=959-4-343-11; 7 = 70 — 63 = 343-3 — 959 —
— (959-4-343-11) = 343-14-959-5. Таким образом, 7=959•«<,+ + 343• V0 при Uo — —5; Vq= 14.
5. Взаимно простые числа. Два целых числа называются взаимно простыми, если их н.о.д. равен 1.
Ясно, что если d есть наибольший общий делитель целых чисел
а и Ь, то -~ и -^- суть целые взаимно простые числа. Действительно, то, что эти числа целые, следует из того, что d — общий делитель для а и Ь. Если б —наибольший общий делитель -^-
и ¦^-, то а и b делятся на do, откуда следует, что 6=1, иначе d
не был бы наибольшим общим делителем для а и Ь.
Предложение 5. Для того чтобы целые числа а и b были взаимно простыми, необходимо и достаточно существование целых чисел Uq, V0 таких, что ЙИо + bvo = 1.
Предложение 5 можно сформулировать и в других терминах: для того чтобы неопределенное уравнение аи + bv = 1 имело решение uo, V0 в целых числах, необходимо и достаточно, чтобы а и b были взаимно просты.
Доказательство. Пусть а и b взаимно просты. Тогда их н.о.д., равный 1, имеет линейное представление: 1 = аи0 + bv0. Пусть теперь существуют Uo и V0 такие, что аи0 + bv0 = 1. Тогда н.о.д.(а, Ь) делит а«о и bvo, а следовательно, и их сумму, равную 1. Но 1 не имеет натуральных делителей, кроме 1, так что н-°-д.(а, Ь) равен 1. Предложение доказано полностью.
