1611703151-03589a55eaf19010bb3ad337d2045391 (827005), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Другими словами, а делится на Ь, если их частное с снова есть целое число. То же отношение делимости а на Ь может быть выражено другими равнозначными терминами: Ь делит а; Ь вЂ” делитель а; а есть кратное для Ь. Из определения делимости ясно, что число О делится на любое целое число,в том числе и на О, но ни одно целое число, отличное от нуля, на нуль не делится. Ясно также, что любое целое число а делится на а, — а, 1 и — 1. Эти числа называются несобственными, или тривиальными, делителями числа а. Остальные же делители, если они есть, называются собственными, или нетривиальными. Запишем теперь в виде предложений 1слово «предложение» значит то же, что слово «теорема», — это высказывание, которое должно быть доказано; мы будем пользоваться словом «теорема» только тогда, когда нужно подчеркнуть важность содержания) некоторые простейшие свойства делимости. П р ед ложе н не 1. Если два иелых числа а и Ь делятся на целое число с, то их сумма и разность тоже делятся на с.

Д о к а з а т е л ь с т в о. Имеем а = сп, Ь = сй, где д и Ь вЂ” целые числа, ибо а и Ь делятся на с, Тогда а ь Ь = сй ~ сй = с(д-+-Ь). )иола й~й целые. Следовательно, числа а ~ Ь делятся на с. целые числя [гл ~ П р е д л о ж е н и е 2. Если целое число а делится на целое число Ь и й — целое число, го ай делится на Ь. Доказательство. Имеем а Ьт при целом т, ибо а делится на Ь.

Тогда ай = Ьтй. Число тй целое. Следовательно, ай делится на Ь, что и требовалось доказать. Это предложение можно сформулировать и так: если с делится на а и а делится на Ь, то с делится на Ь. Действительно, «с делится на а» значит то же самое, что с = аА прн целом Ь. 2.

Деление с остатком. Всем хорошо известно, что если деление целых чисел не выполняется «нацело», то возможно деление «с остатком». Придаднм этому высказыванию точный смысл в виде следующей теоремы. Теорема 3. Пусть а, Ь е= гк (г. е. а и 6 являются целыми числами) и ЬФО. Сугцествуюг целые числа д (неполное частное) и г (остаток) такие, что а = Ьд + г и 0 г ( | Ь | — 1. Эти требования однозначно определяют д и г.

Доказательство. Положим сначала, что Ь О. Рассмотрим рациональное (не обязательно целое) число а = ь . Если оио целое, то положим д = а. Если же а не целое, то найдутся два соседних целых числа, в промежуток между которыми попадает а. Меньшее из них обозначим через в. Тогда у( и ( д+ 1. Итак, в обоих случаях мы нашли целое число у такое, что д( — <д+ 1.

Умножнм все три части этого двойного неравенства на Ь, Так как Ь ) О, знаки неравенства должно сохранить: Ьу ( а ( Ьд+ Ь, откуда 0 ( а — Ьд ( Ь. Положим а — Ьд = г. Это целое число, и, так как г ( Ь, а числа г и Ь оба целые, должно выполняться более сильное неравенство г ( Ь вЂ” 1. Итак, а = Ьу+ г и 0 ( г ( Ь вЂ” 1. Пусть теперь Ь ( О.

Тогда Ь = — )Ь!. Применив предыдущее построение к числам а и |Ь), найдем целые числа у' и г такие, что а = д'!6!+ г, 0(г -|Ь| — 1. Полагая у'= — в, получим а = у( — |Ь|)+ г=дЬ+ г, 0 ( г(|Ь| — 1. Тем самым существование д н г доказано как для положительных, так и для отрицательных Ь. Остается доказать единственности чисел д и г.

Пусть а = = Ьд1 + гь 0( г1 (|Ь! — 1, и а = Ьд~+ гг, О ( г2 -'|Ь! — 1, причем, разумеется, числа а, Ь, дь дв гь г,— все целые. Тогда Ьв, + + г1 = Ьу»+ гг 6 (д~ — дз) = 㻠— гь Положим, что д1 Ф уь Тогда |гз — г1|=|Ь!. |д~ — уз|= |Ь!, нбо |д~ — у»!) 1. С другой стороны, самое большее возможное значение для 㻠— г| есть )6|— — 1 — 0 =|Ь! — 1, самое меньшее: 0 — (|Ь! — 1)= — (|Ь! — 1). Таким образом, — (|Ь| — 1) ( 㻠— г~ е-. |Ь| — 1, откуда |㻠— г, ! ~ '( | Ь | — 1, что противоречит установленному ранее | 㻠— г, | ) ! Ь |.

Мы пришли к противоречию, доназывающему неверность сделан- теооия делимости целых чисел ного предположения д~ чьдь Следовательно, д~ — — до, а тогда и г, = го. Теорема доказана. 3 а м е ч а н и е. По ходу доказательства мы использовали то обстоятельство, что для любого вещественного а (у нас а было рациональным) найдется целое д такое, что д ( а ( ц+ 1. Такое число д называется целой частью сс и обозначается [а).

Напри- мер, [5[ = 5, [и) = 3, [ — 2, 7[ = — 3, 3. Наибольший общий делитель. Пусть а и Ь вЂ” два целых числа, из которых по крайней мере одно отлично от нуля. Наи- большим общим делителем чисел а и Ь называется наибольшее натуральное число д, являющееся делителем как для а, так н для Ь. Например, наибольший общий делитель чисел — 6 и 1О равен 2, наибольший общий делитель чисел — 6 и 0 есть 6, наибольший общий делитель чисел — б и 6 равен 1, Наибольший общий делитель чисел а и Ь обозначается н. о. д. (а, Ь) или просто (а, Ь); последнее обозначение приме- няется только в случае, если в том же контексте символ (а, Ь) не используется в каком-либо другом смысле (например, координаты точки на плоскости или скалярное произведение векторов а и Ь и т.

д.). Важное свойство наибольшего общего делителя сформулиро- вано в следующей теореме. Теорема 4. Пусть а, Ь вЂ” целые числа, одно из которых от- лично от О, и пусто й — их наибольший общий делитель. Тогда (1) существуют целоое числа ио, оо такие, что д = аио+ Ьоо, (2) если й' — какой-либо общий делитель чисел а и Ь, то а' делится на й'. Д о к аз а т ель ство. Рассмотрим бесконечное множество М целых чисел, состоящее из чисел аи+ Ьо, где и н о независимо друг от друга пробегают все целые числа: М = (аи -1- + Ьо[и, не= У). Множество М содержит число а, оно получается при и = 1 ° о=О; М содержит Ь (при и=О, и=1); М содержит О (при и = О, с = О) и бесконечно много других целых чисел.

Установим, что если два числа х н у принадлежат М и уФО, то остаток при делении х на у тоже принадежит М. Действи- тельно, хонМ и у енМ значит, что х= аи1+ Ьоь у = аио+Ьоо прн некоторых целых иь пь им во. Пусть х=уд+г,д, генУ и О < г <)у[ — 1, так что г есть остаток при делении х на у. Тогда г = х — уд = аи, + Ьщ — у(аио+ Ьс,) = а(и1 — уи,)+ Ь(о1 — доо). Числа и, — дио и п~ — дсо целые, следовательно, ген М. Выберем теперь в множестве М наименьшее положительное число й. Покажем, что а и Ь делятся на д. Пусть г1 — остаток прн делении а на а.

Так как а и д принадлежат М, то, в силу 'галька 3то сказанного, г~ принадлежит М. Но О = г, (а, а й— наименьшее положительное число, содержащееся в М. Следова- 1О палые числа )гл. с тельно, г~ не может быть положительным числом, так что г, = О. Это значит, что а делится на д. Те же соображения приводят к выводу, что Ь делится на Н. Таким образом, Н есть общий делитель а и Ь. Далее, так как дев М, существуют целые и«и п«такиэ, что д = аиэ+ Ьо,. Пусть теперь д' — какой-либо общий делитель для а и Ь. Из равенства д = аи«+ Ьо«заключаем, что Ы делится на гг', ибо оба слагаемых правой части равенства делятся на й'.

Поэтому Н ) д', так что Н есть наибольший общий делитель. По ходу рассуждения оказались доказанными оба утверждения теоремы. 4. Алгорифм Евклида. Метод доказательства теоремы 2 очень быстро приводит к цели, но он не дает средства для фактического вычисления И. Предлагаемый способ — найти наименьшее натуральное число в бесконечном множестве чисел М вЂ” совершенно не эффективен. Однако деление с остатком позволяет быстро «спускаться» внутри М к наименьшему натуральному числу, содержащемуся в М, т. е. к наибольшему общему делителю, Именно, поделим с остатком а на Ь (считаем, что Ь ~ О), затем Ь на первый остаток, затем первый на второй и т.

д. Получим цепочку равенств и неравенств: а = Ьц~+ гь О ( г~ =) Ь! — 1, Ь = г~д»+ гь О ( гз «- г~ — 1 и т. д. Каждый последующий остаток есть натуральное число, строго меньшее предыдущего. Поэтому процесс не может продолжаться без конца. Но закончиться он может только на том, что на каком-то шагу деление выполнится без остатка,' Таким образом, а=Ьд, + г„о < г, () Ь) — 1; Ь = г,дз+ гз, О < г2 » (г, — 1; г~ =газ+ гз О < гз <гз — 1' г«. з — — г«п«+ гм О < г»( гэ, — 1; г», = гну«+ь Покажем, что последний отличный от нуля остаток г«равен н,о.д.(а, Ь).

Для этого сначала пересмотрим все равенства снизу вверх: г« ~ делится на г,, г«м как сумма двух чисел, делящихся на гм тоже делится на г«и т. д. К третьему сверху равенству чы придем, зная, что г2 и гз делятся на гз, и заключим отсюда, что г~ делится на г,. Из второго заключим, что Ь делится па г;, из первого — что а делится на г,. Таким образом, а н Ь делятся на г,. Пусть теперь д' — какой-либо общий делитель для а и Ь. Пересмотрим равенства сверху вниз с точки зрения делимости на сГ. Из первого равенства заключаем, что г, как разность двух чисел, делящихся на д', делится на Ы'. Из второго — что га делится на «)' по той же причине, и т.

д. Из предпоследнего заключим, что ТЕОРИЯ ДЕЛИМОСТИ ЦЕЛЫХ ЧИСЕЛ г, делится на д' и, следовательно, го ) д'. Итак, го оказывается общим делителем, причем наибольшим, Изложенный способ отыскания н. о. д. называется алгорифмом Евклида, он известен уже более 2000 лет. В процессе доказательс1ва мы вновь установили свойство (2) н.о.д. Далее, из сказанного ранее ясно, что все остатки ги ге, ..., го принадлежат множеству М, что дает доказательство и свойства (!), причем представление остатков в виде аи+ Ьс легко осуществляется шаг за шагом. Таким образом, алгорифм Евклида дает не только способ вычисления н.о.д.

чисел а и Ь, но и его линейное представление в виде аио+ Ьоо. П ример. Пусть а = 959, Ь = 343, Найти их н.о.д. и найти его линейное представление. Решение: 959 = 343.2+ 273; 343= 273 1+70; 273= 0.3+ 63; 70 = 63 1+ 7; 63 = 7 9+0. Таким образом, д= 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 !1; 7 = 70 — 63 = 343 3 — 959— †(959 4 — 343 11) = 343.14 — 959 5. Таким образом, 7=959 ио + + 343 оо при ио = — 5; оо = !4 3. Взаимно простые числа. Два целых числа называются взи гумно простыли, если их н.о.д.

равен 1. Ясно, что если д есть наибольший общий делитель целых чисел о ь а и Ь, то — и — суть целые взаимно простые числа. Действии тельно, то, что эти числа целые, следует из того, что д — общий а делитель для а и Ь. Если 6 — наибольший общий делитель л и —, чо а и Ь делятся на Ыб, откуда следует, что 6 = 1, иначе д не был бы наибольшим общим делителем для а и Ь. П редложе н не 5. Для того чтобгл целые числа а и Ь были взаимно простыми, необходимо и достаточно существование целых чисел ио, оо таких, что аио+ Ьоо = 1. Предложение 5 можно сформулировать и в других терминах: для того чтобы неопределенное уравнение аи+ Ьо = 1 имело решение ио, о, в целых числах, необходимо и достаточно, чтобы а и Ь были взаимно просты.

Д оказ ател ьство. Пусть а и Ь взаимно просты. Тогда их и.о.д., равный 1, имеет линейное представление: 1= аио+Ьо,. Пусть теперь существуют ио и оо такие, что аио+ Ьоо = 1. Тогда и.о.д,(а„Ь) делит аио и Ьоо, а следовательно, и их сумму, равную !.

Но 1 не имеет натуральных делителей, кроме 1, так что н. и д.(а, Ь) равен 1. Предложение доказано полностью, Предложен не 6. Если целые числа аь ае взаимно просты С целым числом Ь, то их произведение а1ае тоже взаинно просто с Ь. ЦЕЛЫЕ ЧИСЛА |гл. | До к аз а тельство. Сушествуют целые и|, оь иг, ог такие, что а|и|+ Ьо| — — 1, агиг+ Ьог = 1 в силу предложения 5.

Характеристики

Список файлов лекций