Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 22
Текст из файла (страница 22)
Следующая теорема объясняет действие, которое встречается в элемеитариой арифметике. Положительное целое число а можно разделить иа положительиое целое число Ь и получить остаток г, который меньше, чем 6. Например, если 31 делить иа 9, получим частное 3 и остаток 4. К примеру, 31 = 3.9+4, где 4 < 9. Доказательство следующей теоремы также является иллюстрацией принципа полного упорядочения. ТЕОРЕМА 3.28. (Алгоритм деления) Для положительных целых чисел а и 6 существуют единственные неотрицательные целые числа д и г, где О < г < 6 такие, что а = 69+ г.
Такие целые числа т и 9 называются, соответственно, остатком и частным от деления а иа Ь. РАЗДЕЛ 3.4. Делимосюь 141 ДОКАЗАТЕЛЬСТВО. Пусть а и Ь вЂ” положительные целые числа. Рассмотрим множество Я всех неотрицательных целых чисел, имеющих вид а — Ьд' для неотрицательного целого числа 9', т.е. Я = (х: х = а — 69', х > О, и 9' > О) . Множество Я непусто, поскольку для д' = 0 имеем а — 69' = а — 6.0 = а > О, так что а е Я.
Множество Е имеет наименьший элемент, скажем, г', В самом деле, если 0 е Я, он и является наименьшим элементом. В противном случае о содержит только положительные целые числа и, следовательно, согласно принципу полного упорядочения Х5 имеет наименьший элемент. Поскольку т' принадлежит о, пусть д' — неотрицательное целое число такое, что т' = а — 69'. Если г' > Ь, то г" = г' — Ь > 0 и а — 69' = г', а Ьд~ Ь гг 6 а — 6(4 +1) =г так что г" принадлежит Я.
Кроме того, т" < т', так как 6>0, -6<о, т' — 6< г'+О =т'. Но т" < т' и то, что га е Я, противоречит предположению, что т' является наименьшим элементом множества Я. Таким образом, 0 < г' < Ь. Чтобы показать единственность, предположим, что а = 69+ т = Ьр+ з, где 0 < т < е < 6. Поскольку г > О, то — т < О.
Следовательно, з — т < 6+ 0 = Ь. Но з — т = 6(д — р), и по теореме 3.25, если 9 — р не равно О, то з — г > 6. Следовательно, о — р = О, о = р и г = з. Если а < Ь, то 9 должно быть равно О, чтобы выполнялось а = Ьд+ т, где 0 < г < Ь и д > О. Например, для а = 4 и Ь = 7 алгоритм деления дает 9 = 0 и т = а = 4, так что 4 = 7 О+ 4. В силу единственности у и т, если можно получить д и г каким-нибудь другим способом, причем а = Ьд + г, 0 < т < 6 и 9 > О, то эти д и г должны совпадать с теми, которые существуют согласно теореме. Поскольку любой положительный делитель положительного целого числа п не может быть больше самого этого числа, все положительные делители числа и можно найти, перебирая все целые числа от 1 до и и проверяя, не делят ли они и.
Так, например, мы определили, что положительными делителями числа 12 являются числа 1, 2, 3, 4, 6 и 12. Точно так же можно показать, что положительными делителями числа 90 являются 1, 2, 3, 5, 6, 9,10, 15, 18, 30, 45 и 90. Проверка показывает, что числа 1, 2, 3 и 6 являются делителями как 12, так и 90. Числа 1, 2, 3 и 6 называются общими делителями чисел 12 и 90. Более того, 6 есть наибольший из этих общих делителей.
Обратим внимание, что общие делители 1, 2, 3 и 6 являются также делителями наибольшего общего делителя 6. В контексте наибольших общих делителей рассматриваются только положительные делители. 142 ГПАВА 3. погика, целые числа и доказательства ОПРЕДЕЛЕНИЕ 3.29. Положительное целое число д называется общим делителем чисел а и 6, если Ы ( а и Ы ) Ь. Алгоритм нахождения наибольшего общего делителя приведен в главе 7. ТЕОРЕМА 3.31. Если г( и с — наибольшие общие делители целых чисел а и Ь, то с = д; другими словами, существует единственный общий делитель для целых положительных чисел а и Ь. ДОКАЗАТЕЛЬСТВО. По определению наибольшего общего делителя д ! с и с ~ Н. Следовательно, с = г( или с = — д.
Поскольку с и д — оба положительные, то с = а. ТЕОРЕМА 3.32. Наибольший общий делитель положительных целых чисел а и 6 существует. Такой наибольший общий делитель может быть записан в виде и а+и 6 для некоторых целых чисел и и и. Кроме того, наибольший общий делитель— это наименьшее положительное целое число такого вида. ДОКАЗАТЕЛЬСТВО. Пусть Я вЂ” множество всех положительных целых чисел, имеющих форму па+ тпЬ. Пусть д = иа+ и6 — наименьший элемент множества Я.
Тогда д < а, т.к. а = 1. а+ О Ь принадлежит Я. Кроме того, а = дд+ т для некоторых д и т, где д > О и О < т < д. Итак, а = д(па+ иЬ) + т. Решая относительно т, получаем, т = (1 — ди)а + ( — и)дЬ, так что т принадлежит 5 или т = О. Но т меньше, чем д, которое, в свою очередь, является наименьшим элементом множества Я, так что т = О. Поэтому Ы ) а. Аналогично, д ( Ь.
Если с— произвольный делитель чисел а и Ь, то по теореме 3.24 часть (в) с) Ы, поскольку г( = иа+ и6. Следовательно, г( — наибольший общий делитель чисел а и Ь. ° Алгоритм нахождения и и и приведен в главе 7. Свойства наибольшего общего делителя, которые сформулированы в следующей теореме, будут использованы в дальнейшем. ТЕОРЕМА 3.33.
Если а = Ьд+ с, то НОД(а, Ь) = НОД(6,с); другими словами, каждый делитель а и Ь является делителем Ь и с, и обратно. ДОКАЗАТЕЛЬСТВО. Пусть е = НОД(а,Ь) и 7 = НОД(6,с). Поскольку е ! а и е ) Ь, то по теореме 3.24(в) имеем е ( с, т.к. с = а — Ьд. Тогда, по определению наибольшего общего делителя е ~ г'. Обратно, поскольку 7 ) Ь и 7" ( с, то по теореме 3.24(в) 7' ! а.
По определению наибольшего общего делителя 7' ~ е. Следовательно, е = 7". РЯЗДЕЛ 3.4. Делимость 143 ТЕОРЕМА 3.34. Если а, Ь и с — целые числа, НОД(а, Ь) = 1 и а ) Ьс, то а ( с. ДОКАЗАТЕЛЬСТВО. Поскольку НОД(а, 6) = 1, то существуют целые числа и и и такие, что аи + Ьи = 1. Умножим каждое слагаемое на с, получая сои+ сЬи = с. Тогда а ( саи и а ( сЬи, т.к, а ) 6с. Следовательно, а ( с. ОПРЕДЕЛЕНИЕ 3.35. Если наибольший обший делитель а и Ь есть 1, то числа а и Ь называются взаимно простыми. Непосредственно из определения следует, что если а и 6 — взаимно простые числа, то сушествуют целые числа и и и такие, что аи+ Ьи = 1.
Заметим, что если а и Ь вЂ” положительные целые числа, то а6 кратно и а, и 6. Если рассматривать множество всех чисел, кратных а и 6, то согласно принципу полного упорядочения сушествует наименьшее кратное чисел а и Ь. Если с— наименьшее кратное чисел а и Ь, а Н вЂ” другое кратное чисел а и Ь, то с ~ Н. Иначе говоря, существуют д и г такие, что й = цс+ г, где г ( с.
Поскольку и а, и 6 делят числа й и с, они также делят г. Но тогда г было бы кратным а и 6, которое меньше, чем с, что приводит к противоречию. Таким образом, мы приходим к следующим определениям. ОПРЕДЕЛЕНИЕ 3.38. Положительное целое число т называется общим кратнын целых чисел а и Ь, если а ~ гп и Ь | т. Использование наибольшего общего делителя оказывается полезным при нахождении решений уравнений вида ах+Ьу = с или для доказательства, что такие решения не сушествуют. Это вытекает из приведенной ниже теоремы.
Алгоритм для нахождения х и у приведен в главе 7. ТЕОРЕМА 3.38. Уравнение ах + Ьу = с, где а, Ь и с — целые числа, имеет целочисленное решение (т.е. существуют целые числа х и у такие, что ах + Ьу = с) тогда и только тогда, когда с делится на НОД(а,6). Если с делится на НОД(а, Ь), то решение ах + Ьу = с имеет вид и с НОД(а,6) ' НОД(а, 6) где и и и — любые решения уравнения НОД(а,6) = пи + Ьи. 144 ГПАВА 3, погцке, целые числе и доказательстве ДОКАЗАТЕЛЬСТВО.
Известно, что существуют целые числа и и и такие, что аи+ 6и = НОД(а,Ь). Если с делится на НОД(а,Ь), то с = е НОД(а,6) для некоторого целого числа е. Следовательно, аие+ Ьие = е НОД(а,Ь) = с, так что х = и е и у = и е — решения уравнения. Обратно, если существуют х и у такие, что ах+ Ьу = с, то, поскольку НОД(а, 6) делит как а, так и 6, он делит ах+ Ьу и, следовательно, делит с. ° УПРАЖНЕНИЯ 1.
Найдите положительные делители каждого из следующих целых чисел: а) 54; б) 63; в) 72; г) 73; д) 74. 2. Для положительных целых чисел а и 6 найдите неотрицательные целые числа д и т, где 0 < т < Ь таковы, что а = 69+ т. а) а=54,6=27; б) а=47,Ь=47; в) а=93,6=17; г) а=43, Ь=8; д) а=33,Ь=1. 3. Для положительных целых чисел а и Ь найдите НОД(а,Ь), НОК(а,6) и НОД(а,Ь) НОК(а,6), если они определены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
