А.И. Галочкин, Ю.В. Нестеренко, А.Б. Шидловский - Введение в теорию чисел (1159516), страница 3

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

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

При а+Ь=2 имеем, что а=1, Ь=1, (а, Ь) =1, и утверждение выполняется. Предположим, что оно справедливо для всех пар а, Ь, (а, Ь) =1, с суммой а+Ь<Ь, Ь>2. Докажем, что тогда оно имеет место и для пар а, Ь, (а, Ь) =1, с суммой а+Ь=А, Из условий (а, Ь) =1, а+Ь>2 следует, что аФЬ, Ввиду симметрии равенства (1) для определенности можно считать, что а>Ь. Тогда из равенства (1) имеем, что (а — Ь)и=Ь(о — и), (а — Ь, Ь) =1, (2) н сумма (а — Ь)+Ь=а<Ь.

Поэтому по предположению индук- ции нз равенства (2) следует, что Ь(и, н по определению дели- мости и=и1Ь. Подставляя это значение в равенство (1) и со- кращая обе его части на Ь, получим, что аи,=о, откуда следует, что а(о. Утверждение доказано. Лемма 3 для натуральных а, Ь и с следует из доказанного утверждения. Если (а, Ь) =1 и Ь(ас, то ас=Ьд и по доказан- ному Ь(с. Л ем м а 4. Если целое число Ь взаимно просто с каждым из целых чисел а, а„, то Ь взаимно просто с их произведе- нием а~ ...

а„. До каз а тельство. Проведем доказательство с помощью индукции по и. При п=! утверждение очевидно. Допустим, что п>1 и для значения и — 1 утверждение доказано. Если д — об- щий делитель чисел Ь и а,.... а„, то (д, а„) =1 и из леммы 3 следует, что а'1а~ ... а,. По индуктивному предположению (Ь, а,.....а„1) =1.

Значит, д=1. Лемма доказана. Если а не делится на Ь, то принято говорить о делении а на Ь с остатком. Теорема о делении с остатком. Если а и Ь вЂ” це- льче числа, Ь>0, то существуют единственные целые числа д и г такие, что а=Ьйу+г, Ок:г<Ь. (3) Доказательство. Существует наибольшее целое о такое, что Ьд~а. Тогда Ьд~а<Ь(д+1), откуда О~а — Ьг7<Ь. Обозначая а — Ьд=г, получаем представление (3).

Докажем единственность этого представления. Если кроме представления (3) имеется другое представление а=Ьо,+гь 0<г,<Ь, (4) то из равенств (3) и (4) находим, что О=Ь(о — о1) +г — гь ) г — г,1 <Ь. (5) Из равенства (5) следует, что число Ь делит разность г— — гь Но ~!г — г~!<Ь и поэтому г=гь а тогда из равенства (5) получаем о=он Теорема доказана. Число д в равенстве (3) называется неполным частным при делении а на Ь, а г — остатком от деления а на Ь, Если в равенстве (3) г=О, то это означает, что Ь(а. П р и м е р ы.

Пусть Ь=12. Полагая а=110, — 53, !56, находим ! !О= !2.9+2, 0<2<12, — 53=12. ( — 5)+7, 0<7<12, 156=12 !3+О, 0<12. $2. Простые числа Рассмотрим множество натуральных чисел Ь!. Число 1 имеет единственный натуральный делитель. Каждое натуральное число п, п>1, делится на 1 и п. Натуральное число и>! называется простым, если оно не имеет других натуральных делителей, кроме 1 и и.

Натуральное число и называется составным, если оно имеет .натуральный делитель, отличный от 1 и и. Из этого определения следует, что каждое составное число представляется в виде п=аЬ, а, Ье-=й(, 1<а<и, 1<Ь<п. В этом параграфе будем рассматривать только натураль.ные делители целых чисел. Л е м м а 5. Наименьший отличный от единицы делитель натурального числа п>1 есть простое число. Доказательство.

Число п>1 имеет хотя бы два различных делителя н, следовательно, имеет делитель, отличный от !. Среди всех делителей п, отличных от 1, имеется наименьший. Пусть это будет д. Число д должно быть простым, так как в противном случае оно было бы составным и по опреде.лению имело бы делитель о1 такой, что !<4,<д. Но о1(д и .д(п, а тогда по лемме 1 о,~и.

Это противоречит тому, что д— наименьший делитель п. Значит, д — простое число, !3 Следе т в и е. Каждое натуральное число п>1 имеет хотя бы один простой делитель. Л е м м а 6. Наименьший простой делитель составного числа п не превосходит 1'и. Д о к а з а т е л ь с т в о. Пусть р, р>1 — наименьший делитель п, являющийся по лемме 5 простым числом. Так как и— составное число, то п=рЧ, где Ч>р. Поэтому парт. Отсюда, следует, что р <уп.

Ле им а 7. Если р — простое число, то любое целое число а либо взаимно просто с р, либо делится на р. Д о к а з а т е л ь с т в о. Наибольший общий делитель (а, р) является делителем р и поэтому может быть равен только ! или р. В первом случае а взаимно просто с р, а во втором — а делится на р. Основная теорем а арифметики, Любое натуральное число п>1 представляется в виде произведения простых чисел, причс.н единственньчм образом, если не учитывать порядок следования сомножителей.

Доказательство. По лемме 5 число и имеет наименьший простой делитель р,. Тогда п=р,аь Если а,>1, то аналогично получим а1=рзам где рз — наименьший простой делитель числа а, н т. д. Поскольку числа аь аь... убывают, то на некотором шаге будем иметь, что а,=1 и а„~ — — р,. Перемножая все полученные равенства, после сокращения на а~аз. а,, получим разложение числа и на простые сомножители (6) п=р,рз. ° .р,. Докажем теперь единственность разложения (6).

Предположим, что для некоторого и имеются два разложения на простые множители Р1рз' 'Рь=Ч1Чз' 'Ч' (7)' ПРаваЯ часть этого Равенства делитсЯ на Чь Значит, и его левая часть делится на Чь Тогда по лемме 4 хотя бы один из сомножителей левой части делится на Чь Пусть это будет рь Тогда р,=у„так как р, делится только на 1 и рь Сокращая обе части равенства (7) на р1=Чь получим, что Рз' ' 'Рь=уз' ' 'Ч . (8) Повторяя проведенное рассуждение для равенства (8), полУчим Рг=уз и Рз" Рл=уз".Ч, и т.

д., до тех поР пока в одной из частей получающихся равенств, например правой, сократятся все сомножнтелн. Но тогда и в левой части должны сократиться все сомножители, так как равенство р,,1 . Рь=! невозможно, поскольку все числа р,+ь ...,Р„больше единицы Следовательно, в равенстве (7) разложения совпадают. Теорема доказана. Пусть п>1 н равенство (6) есть разложение и на простые сомножители.

Среди чисел рь р, р„могут быть и одинако- 14 вые. ПУсть Рь Рсь...,Рь — Различные из этих чисел, а аь ам... ...,ад — кратности, с которыми они входят в разложение (6). Тогда равенство (6) можно переписать следующим образом: и — р7' р~~' ' ' Рьь (9) Представление (9) называется каноническим разложением .натурального числа п>1 на простые сомножители. П р и м е р. 26!360=2'Зь 5 11'. С помощью канонического разложения (9) можно представить все делители и. Они имеют вид д'= Ра ~ф ...

Раьь, 0(]3, -(сне, 1 — 1, ..., и. (10) Действительно, если Н]п, то по лемме 1 каждый простой делитель числа д делит и. Поэтому он содержится среди чисел рь...,р„ н входит в каноническое разложение числа д в степени, не большей, чем в разложении (9) числа и. Поэтому д представляется в виде (10). Очевидно и обратное, что каждое число вида (10) есть делитель и. В дальнейшем потребуются две функции, часто рассматриваемые в теории чисел. Пусть х — любое действительное число. Обозначим [х]— .наибольшее целое число, не превосходящее х.

Тогда [х] ~х<[х]+1. Функция [х] называется целой частью числа х. Функция (х)=х — [х] называется дробной частью числа х, .Всегда 0 <(х)<1. Очевидно, что (х) является периодической функцией с периодом 1, т. е. прн любом а~У (х+ а) = (х). Установим вспомогательное предложение, с помощью которого находится каноническое разложение числа и! Л е м м а 8, Показатель а„=сер(п), с которым простое число р входит в каноническое разложение числа пй определяется ривенством (11) 3 а м е ч а н и е. Ясно, что сумма в правой части равенства (11) будет конечной. Все слагаемые, для которых р'>п, равны нулю. Гл! Д о к а з а т е л ь с т в о.

Среди чисел 1, 2,., и имеется Р л .делящихся на р, среди таких ~ — ~, делящихся на рэ, а сре- ( Р' 15 Число й! не делится ни на одно из простых чисел 2, 3, 5...,р, так как прн делении Л' на любое из этих чисел остаток равен 1. Но й!>! н по следствию из леммы 5 М должно иметь простой делитель. Полученное противоречие показывает, что сделанное предположение не верно и теорема справедлива. Занумеруем простые числа р,=2, р,=З,...,р ... в порядке их возрастания. Доказательство теоремы Евклида позволяет получить грубую оценку для числа р„.

Докажем по индукции, что р„,,(2", п=!,2, (13): При п=( утверждение (!3) верно, рз=З<2'. Допустим, что оно выполняется для п — 1, и докажем, что тогда оно имеет место и для и. Поскольку р„э, не больше наименьшего простого делителя числа р,р, ... р„+1, а р,=2, то р„+, ~<р1ре ° р„+ 1 ч 2'~ ~"'+' + ! е 2'". (14) 2, З,...,й!. Число 2, являющееся простым, оставляем и зачеркиваем после него все четные числа. Первое следующее за 2 незачеркнутое число есть 3. Оно не делится иа 2. Значит, оно не имеет делителей, отличных от 1 и 3, и поэтому является простым. Оставляем 3 и зачеркиваем после него все числа, кратные 3.

Продолжая этот процесс, найдем все простые числа, не превосходящие некоторого простого числа рм При этом будут зачеркнуты все составные числа, кратные 2, 3, ..., рм Первое незачеркнутое после р„число будет простым числом р~~ь так как оно не делится на 2, 3, ...,рх и поэтому. имеет делителями только 1 и речь Если найдено рх>)%, то все оставшиеся незачеркнутыми числа будут простыми, поскольку все кратные чисел 2, 3, ...

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

Список файлов книги