Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 23
Текст из файла (страница 23)
а) а=54,6=27; б) а=17,Ь=О; в) а=6,6=15; г) а=12,Ь=16; д) а=33,Ь=1. 4. Докажите или опровергните утверждение: для положительных целых чисел а и 6 НОД(а,6) < НОК(а,6). 5. Если а = 0 или Ь = О, то что можно было бы принять в качестве НОК(а, Ь)? Ответ обоснуйте. 6. Докажите, что для взаимно простых чисел а и Ь и заданного целого числа и существуют целые числа х и у такие, что ах+ Ьу = и. 7. Докажите, что для положительных целых чисел а и Ь, если а > Ь, то НОД(а, 6) = НОД(а — Ь, 6).
8. Рассмотрим теорему; если целые числа а и Ь таковы, что а ( 6 и Ь ) а, то а = Ь или а = — Ь. Докажите, что эта теорема также справедлива в случае, когда а < 0 и Ь < О. 3.5. ПРОСТЫЕ ЧИСЛА Очевидно, что каждое целое число а делится само на себя и на 1, т.к.
а = 1 а. Каждое целое число делит О, но 0 не делит никакое целое число. Для некоторых задач теории чисел необходимо знать, имеет ли некоторое конкретное целое число делители, отличные от него самого и 1. Некоторые целые числа не могут быть разложены в произведение целых чисел, исключая тривиальный способ. Такие целые числа называются простыми. ОПРЕДЕЛЕНИЕ 3.39.
Целое число, большее 1, называется простым, если оно не имеет положительных делителей, кроме 1 и самого себя. Положительное целое число, большее 1, называется составным, если оно не является простым. РАЗДЕЛ З.о. Простые числа 145 Среди первых 10 положительных целых чисел имеется четыре простых числа: 2, 3, 5 и 7. Целые числа 4 = 2. 2, 6 = 2 3, 8 = 2. 4, 9 = 3. 3 и 10 = 2 5 являются составными. Итак, если и = г а, где 1 < г < и и 1 < а < п, то и— составное число.
По определению, целое число 1 не является ни простым, ни составным. Число 2 — единственное четное простое число. Определить, является ли небольшое целое число простым, пытаясь разделить его на меньшие простые числа, сравнительно легко, т.к. количество возможных вариантов невелико. Однако, вопрос о том, является ли простым большое целое число, может оказаться достаточно сложным. Следующая теорема показывает, что существует бесконечно много простых чисел.
Доказательство теоремы является классическим примером использования принципа сведения к абсурду. ТЕОРЕМА 3.40. (Евклид) Существует бесконечно много простых чисел. ДОКАЗАТЕЛЬСТВО. Допустим, что существует только конечное число простых чисел, напРимеР, Ры Рз, ..., Рь. РассмотРим целое число (Р1Рз - Рь) 1 1. ПРедположим, что р„— некоторое простое число, и р, ( ((ргрз Рь) + 1). Но тогда Р~ ~ МРз. Рь), откуда следует, что Р„~ 1, а это приводит к противоречию, т.к р„> 1.
Следовательно, (ргрз рь) + 1 — простое число, что, в свою очередь, также является противоречием, т.к. этого числа нет среди указанной конечной совокупности простых чисел. Таким образом, наше предположение о том, что существует конечное число простых чисел, ложно, поэтому простых чисел должно быть бесконечно много. Поскольку разложение целых чисел на простые множители является важной задачей, необходимо иметь быстрый и простой способ определения, является ли данное положительное целое число простым или составным. Следующая теорема показывает, что для проверки простоты числа необходимо определить только некоторые из его возможных делителей. ТЕОРЕМА 3.41.
Если положительное целое число п является составным, то и имеет простой делитель Р такой, что рз < п. ДОКАЗАТЕЛЬСТВО. Пусть Р— наименьший простой делитель числа п. Если п раскладывается на множители г и а, то р < г и Р < а. Следовательно, р~ < га = и. Например, чтобы определить, является ли и = 521 простым, необходимо рассмотреть только простые числа, которые меньше или равны 22, потому что 22~ = 484, а 23з = 529. Простые числа, меньшие или равные 22, — это 2, 3, 5, 7, 11, 13, 17 и 19. Проверяя каждое из них, находим, что ни одно из них не делит 521. Поэтому 521 является простым числом в силу предыдущей теоремы.
Как покажет следующая теорема, простые числа образуют множество своего рода строительных блоков для целых чисел. ТЕОРЕМА 3.42. Каждое положительное целое число либо равно 1, либо простое, либо может быть записано как произведение простых чисел.
146 ГЛД8А 3. Логика, целые числа и доказательства ДОКАЗАТЕЛЬСТВО. В доказательстве этой теоремы использован второй принцип индукции. Несомненно, теорема справедлива для и = 1. Допустим, что она справедлива для всех положительных целых чисел ги, меньших, чем )ч Если й— простое, то теорема справедлива также и для к. Если к не является простым, то оно делится на некоторое простое число р и к = р9, где и р, и 9 не могут быть равными к или 1. Поскольку согласно теореме 3.25 числа р и д меньше, чем Ь, то по индуктивному предположению они либо простые, либо могут быть записаны как произведение простых чисел. Следовательно, й = рд может быть записано как произведение простых чисел. Целое число 37 — простое.
Целое число 1554985071 = 3 3 4463 38713— произведение четырех простых чисел, два из которых совпадают. Следующая теорема показывает, что если некоторое целое число и делится на простое число р, то невозможно разложить и на множители таким образом, чтобы р не был делителем по крайней мере одного из этих множителей.
ТЕОРЕМА 3.43. Если р — простое число и р ! аЬ, где а и Ь вЂ” положительные целые числа, то р ) а или р ( 6. ДОКАЗАТЕЛЬСТВО. Если р ) а, то утверждение теоремы имеет место. С другой стороны, предположим, что р не делит а. Поскольку р и а — взаимно простые, то существуют и, е такие, что ри+ ап = 1. Поэтому риЬ+ аиЬ = 6. В силу того, что р ) риЬ и р ) або (т.к. р ) аЬ), имеем р ) Ь. ЛЕММА 3.44. Если простое число р делит произведение положительных целых чисел 419з. 9„, то р делит 4, для некоторого г, 1 < 1 < и. ДОКАЗАТЕЛЬСТВО. В доказательстве леммы использована индукция по и, числу множителей в произведении.
Если и = 1, правильность леммы очевидна. Допустим, что лемма верна для и = к. Это означает, что если р делит произведение любых к целых чисел, то р делит один из й множителей. Предположим, что р делит произведение Й + 1 целых чисел, скажем, р ~ цгада 9ьдьч.ы так что р ~ ИгЧг 9ь)дь+м Если р делит 9ьч.ы то доказательство завершено.
Если р не делит 9ьчы то по теореме 3.43 имеем р ! (91 . дь). Но поскольку 9г .. 9ь — произведение й целых чисел, то по индуктивному предположению р ~ 9, для некоторого 1 < 1 < )и Следовательно, р ~ д, для некоторого г, 1 <1< )с+ 1. ЛЕММА 3.46. Если простое число р делит произведение простых чисел ды 9з, ..., д„, то р = 9, для некоторого г, 1 < 1 < и.
ДОКАЗАТЕЛЬСТВО. Согласно лемме 3.44, р делит д; для некоторого 1 < 1 < и. Поскольку числа р и 9, — простые, то р = д,. Из совокупности теорем, приведенных выше, получаем главный результат этой главы, который известен как основная теорема арифметики, или теорема о единственности разложения на простые множители. ТЕОРЕМА 3.46. (Основная теорема арифметики) Любое положительное целое число, большее, чем 1, либо является простым, либо может быть записано в виде произведения простых чисел, причем это произведение единственно с точностью до порядка сомножителей.
РАзяел 3.5, простые числа 147 ДОКАЗАТЕЛЬСТВО. Допустим, что 9192 9„и р1рг р, — два способа записи положительного целого числа т как произведения простых чисел. В доказательстве теоремы будет использована индукция по п, числу простых сомножителей в первом произведении. Если п = 1, теорема тривиально верна. Сформулируем индуктивное предположение: пусть теорема верна, когда 9192 ..9ь = р1рг р.; т.е если т = 9192 9ь = р)рг р„то й = з и произведение единственно с точностью до порядка простых сомножителей. Предположим теперь, что т = а1аг аь41 = ргрг .р;.
Поскольку оь4.1 делит ргрг .р,, отсюда следует, что 9ь4.1 = р, для некоторого 1 < 4 < з'. Разделим оба произведения на дь4.1 или используем свойство сокращения (аксиому 18). Тогда 9192. ф, = р(рг...рг )р1е)...р;. Но по индукции /с = з' — 1, и произведение единственно с точностью до порядка простых сомножителей. Следовательно, к+ 1 = з', и разложение на множители числа т единственно с точностью до порядка простых сомножителей. Например, и = 39616304 = =2 13 7 2.23.13 2 13 2.7= =2 2 2 2 7.7 13.13 13.23 представляют собой два разложения на множители числа и; однако, в каждом из произведений одно и то же простое число использовано одинаковое число раз. Различается только порядок записи простых чисел.
Фактически имеется 12,600 различных способов разложения на множители числа и с использованием 10 простых сомножителей, однако, каждое такое разложение содержит ровно четыре двойки, две семерки, три множителя, равных 13, и один, равный 23. Обычно простые множители группируют, используя экспоненциальную запись. Например, 2472133231 СЛЕДСТВИЕ 3.47. Каждое положительное целое число, большее 1, может быть Ь(1) Ь(2) Ь(о) записано единственным образом с точностью до порядка в виде 91 ~дг д„~ где к(1), )4(2), ...
и к(п) — положительные целые числа. Теперь понятно, почему 1 не входит во множество простых чисел. В противном случае теорема о единственности разложения на простые множители была бы неверна. При изучении разложения различных целых чисел, используя их представление, данное в предыдущем следствии, зачастую для удобства обозначения допускается нулевая степень простого сомножителя.
Обычно такая практика не приводит к путанице, т.к. при 9," = 1 всегда 91 > 1. Если разложение на простые множители известно, то простые числа, формирующие разложение на простые множители любого делителя этого числа, образуют подмножество соответствующего множества для делимого. Доказательство двух следующих теорем предоставляется читателю. ТЕОРЕМА 3.48. Если а = Р,( )...Рь( ) и Ь | а, то Ь = Р1( ) . Рь~ ), гДе 0 < Ь(1) < а(1) для всех 1; и обратно. 148 ГЛЛВА 3, Логика, целыг числа о доказательства ТЕОРЕМА 3.49. Пусть а = р ~ )р"~ )р~~ ~ р'.~ ) и Ь = р, р~~ ~рз' ~ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
