Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 52
Текст из файла (страница 52)
Если разделить числа 91 и 203 на их наибольший общий делитель 7, получим т' = 13 и гоз = 29. Легко видеть, что целые числа 13 и 29 — взаимно простые; т.е. НОД(13, 29) = 1. Таким образом, оказалось, что результаты деления двух целых чисел на их наибольший общий делитель не имеют общих делителей, за исключением 1. Доказательство следующей теоремы предоставляем читателю. ТЕОРЕМА 7.8. Пусть заданы целые числа а и Ь, не равные нулю, тогда числа а ь 7 и ь нод ь и йбд — ~ь> являются взаимно простыми, т.е.
НОД ~нбд— , ь>, нод( ь)) = 1. Было определено ранее, что положительное целое число пт представляет собой наименьшее общее кратное целых чисел а и Ь при условии, что (а) а [ т и 6 [ т, и (б) если и — любое общее кратное чисел а и Ь, то пь [ п. Наименьшее общее кратное чисел а и Ь обозначим НОК(а, Ь). Необходимо построить алгоритм нахождения наименьшего общего кратного двух целых чисел.
Цель достигается определением наибольшего общего делителя этих чисел (алгоритм нахождения которого уже имеется) и использованием теоремы 3.50. Указанная теорема утверждает, что для положительных целых чисел а и 6 НОД(а, Ь) . НОК(а, Ь) = аЬ. РАЗДЕЛ 7.3. Алгоритмы деления и алгоритм Евклиде 305 Для нахождения НОК(91, 203) сначала определим НОД(91,203), воспользовавшись алгоритмом Евклида, как зто было сделано ранее, а затем разделим на него произведение чисел 91 и 203. Поскольку НОД(91,203) = 7, находим НОК(91,203) = = 2639. 7 ° УПРАЖНЕНИЯ 1.
Задан алгоритм деления а = Ьд+ г. Найдите д и т для указанных ниже значений а и 6: а) а=75,6=8; б) а=102,6=5; в) а=81, Ь=9; г) а=16,6=25. 2. Найдите наибольший общий делитель для следующих пар чисел; а) 75, 25; б) 27, 18; в) 621, 437; г) 289, 377; д) 822, 436. 3. Найдите наименьшее общее кратное для пар чисел из упражнения 2. 4. Для приведенных ниже пар чисел а и Ь найдите и, и и г( такие, что аи+Ьи = Н, где Н вЂ” наибольший общий делитель чисел а и 6; а) 83,17; б) 361, 418; в) 25, 15; г) 81,9; д) 216,324. 5.
Докажите, что если НОД(а, 6) выражен как ах+ Ьу, то х и у — взаимно простые числа. 6. Докажите, что для целых чисел а и Ь, не равных нулю, но, и йбЯ--„— взаимно пРосты, т.е. НОД (71бф;-~), 1тбдь( — -) = 1 (теоРема 7.8). 7. Запишите в псевдокодах процедуру нахождения согласно алгоритму деления величин д и г, когда произвольное положительное целое число а делится на произвольное положительное целое число 6. 8.
Запишите в псевдокодах процедуру для алгоритма Евклида. 9. Задано целое число а и положительное целое число Ь. Докажите, что целые числа, произведение которых равно а и наибольший общий делитель которых равен 6, существуют тогда и только тогда, когда Ьз ! а. 10. Предполагая, что Г(й) = 2~ + 1 при й > О, а) докажите, что Г(т+1) = Г(0)г(1)г(3) Г(т)+2 для каждого т > 0; б) докажите, что Г(т) и г'(и) — взаимно простые числа, если т ф п.
11. Покажите, что если НОД(а,6) выражен как ах+Ьу, то х и у не определяются единственным образом. 12. Докажите, что если НОД(а, Ь) = 1, то НОД(а+ п6,6) = 1. 13. Докажите, что и. НОД(а, 6) = НОД(па, пЬ). 14. Пусть 5 — множество всех целых чисел вида ах+Ьу. Покажите, что НОД(а, Ь) делит все элементы множества 8. 306 ГЛАВА 7. Теория чисел 7.4. ЦЕПНЫЕ ДРОБИ В данной главе алгоритм деления и алгоритм Евклида будут применяться доста- точно часто. Рассмотрим сначала рациональные числа а/6, где а и Ь вЂ” целые числа и Ь ) О. Если алгоритм деления применен к целым числам а и Ь, где 6 ) О, то существуют единственные целые числа с (частное) и т (остаток) такие, что а=6 с+т при 0<т<6.
Для а = — 124 и 6 = 35 имеем — 124 = (35)( — 4) + 16. ~ — 121 ~ Б1=' при этом дробный остаток т/Ь обладает свойством 0 < т/Ь < 1, Если т ф О, равенства можно переписать следующим образом: а 1 — 124 1 — = 2+ — и — = — 4+ Ь Ь/т 35 35/16 ' где Ь/т > 1. Алгоритм деления можно применить снова и получить 6 = тМ' + т' и 35 = (16)(2) + 3. Таким образом, обращая дробный остаток и применяя алгоритм деления снова и снова, указанным способом получаем выражение рационального числа -124/35: -124 16 1 35 35 35 1 1 — -4+ 3 — -4+ 1 2+— 16 16 2+— 1 = — 4+ 1 2+ (22-) Поскольку дробь 1/3 имеет числителем 1, нельзя далее сокращать 3/1, используя алгоритм деления. Выражение 1 — 4+ 1 2+ 5+— 3 Переписав последние два равенства и перейдя к рациональным числам, получаем а т — 124 16 — =с+ — и = — 4+ — . 6 Ь 35 35 Воспользовавшись функцией целой части числа, отношения можем переписать в таком виде РАЗДЕЛ 7.4.
Цепные дроби 307 называется цепной дробью и представляет собой альтернативный способ записи рационального числа -124/35. В связи с тем, что цепная дробь имеет регулярную структуру и числители всегда равны 1, для точного задания цепной дроби необходимо упомянуть только числа — 4, 2, 5 и 3, поэтому записываем †1/35 = ] — 4;2,5,3]. Числа — 4, 2, 5 и 3 называются элементами цепной дроби или неполными частными, поскольку порождены алгоритмом деления. Точка с запятой отмечают особую природу первого члена — 4.
Например, ]3; 7] = 3+ 1/7 = 22/7, но ]О;3,7] = О+ = 7/22. 1 3+— 7 Возврашаясь к цепной дроби — 124/35 = ( — 4; 2,5,3], замечаем, что 3 = (3 — 1) + 1 = (3 — 1) + 1/1. Таким образом, можно записать — 124 1 — = — 4+ 35 1 2+ 5+— 1 2+— 1 1>у1 =х — 1х] =х — то>0 есть так называемая дробная часть х. Если х1 = 1/уы тогда 1 х = ]х] + Рг = то+ у1 =1о+— х1 11 = ]хг], у2 = хз — ]х1] и х2 = 1/у2, т.к. р2 > О.
тогда х2 > О. Сочетание этих равенств дает и хг > 1. Пусть 1 х1 =т~ + —, где Х2 1 1 х = та+ — = 1о+ х1 1 11 +— Х2 так что запись — 124/35 = ] — 4; 2, 5, 2, 1] тоже имеет место, однако в ней на последнем шаге алгоритм деления не использован. Пример подсказывает, что каждое рациональное число имеет два различных представления в виде цепной дроби с целыми числами в качестве элементов: в одном представлении последний элемент больше 1, а в другом — равен 1, Если х — действительное, но не рациональное число, алгоритм деления не применим; однако, используя функцию целой части, можно получить представление х в виде цепной дроби длины и способом, аналогичным рациональному случаю. Таким образом, для действительного, но не рационального числа х имеется единственное число го, где ~о < х < го + 1 такое, что то = ]х].
Тогда 308 ГЛАВА Т. Теория чисел Продолжая в том же духе, получаем х= го+ 1 11 + 1 тг+ гз+.. + зь,+— хь где т, — целое число для каждого г, т, > 0 для г > 1, хь — иррациональное действительное число и хь > 1. Можно также записать х = [го', т1 тг,, ть м хь]. Например, пусть х = ъ 3 = 1.7320508 . Построим представление числа х в виде цепной дроби следующим образом: Зо = [х] = 1ъГЗ~ = 1, где у1 =х — [х] =х — за = ъ'3 — 1; х, =1/у, = 1/[ъЗ вЂ” Ц = (ъЗ+1)/2; 11= [х1] =1, где уг = х1 — [х1] = х1 — З1 = (ъГЗ + 1)/2 — 1 = (ъ/3 — 1)/2; хг = 1/уг = 2/(ч 3 — 1) = ъ'3 + 1; зг= [хг] =2, где Уз = хг — [хг] = хг — тг = (ъГЗ + 1) — 2 = ъ/3 — 1; хз = 1/Уз = 1/(ъ'3 — 1) = (ч 3 + 1)/2, таким образом, ъГЗ = [Зо, х1] = [1; (ъГЗ + 1)/2] = [Зо тых2] [то~ [11 х2П [1; 1, (ъ/3 + 1)] = = [то,'тытг,хз] = [1о, зы [тг,'хз]] = [1; 1,2, (ъ/3+ 1)/2].
Но поскольку хз = хы структура повторяется, поэтому ъ 3 = [1; 1, 2, 1, 2, 1, 2, ( ъГЗ + 1) /2] и т.д. Отсюда выводим следующее рекурсивное определение цепной дроби. РАЗДЕЛ 7.4. Цепные дроби 309 ОПРЕДЕЛЕНИЕ 7.9. Для конечной последовательности го,г~,тг,...,г„действительных чисел, где п > О и г, > О для г > 1, определим конечную цепную дробь [го,ам Гг,...,1„] следующим образом: [то;] = го,' 1 [го, '1~] = го + — ; [Го'1~ Гг, Гь[ = [Го' [1Ы Гг,,гь)) для 1 < й < п.
Числа го,1ы...,т„называются неполными частными, или элементами цепной дроби. цепная дробь [го, .г„гг,..., г„[ называется простой, если г, — целое число для каждого ю', т.е. каждый элемент цепной дроби есть целое число. Числа [Го,'], [то',Сг], [Го',Г),Гг), ..., (Со,'1~,сг,,гь],, [то'Г~,тг,...,1„) называются подходящими дробями цепной дроби [Го;Г~,тг,,8 ] [Го,'1ь,1г,,Гь], где есть Ь-я подходящая дробь при О < й < и. Для удобства обозначения запись [1о., гы аз,...,8ь], использованная прн Й = О, будет означать [Го,]. Будем говорить, что две цепные дроби [го,аы1г,...,8„] и [Ьо,Ь„Ьг,...,Ь ] равны почленно, если п = т и 1; = 6; при О < 1 < и. Если х — действительное число и х = [го,г„1г,...,1„], тогда будем говорить, что [го;выгг,...,т„[ есть представление цепной дробью числа х.
Два представления называются совпадающими, или равными, если они равны почленно. Следующая теорема дает иной способ разложения цепной дроби на подходящие дроби. ТЕОРЕМА 7.10. Если и — положительное целое число и [1о, тыгг,..., т„] — цепная дробь, тогда для каждого Ь, 1 < й < и, [Го гыег~ ° ° ° ~Го] = [10~ СНГг ° ° ~гь-1 [1ь~Гььы ° ~тп]] ° ДОКАЗАТЕЛЬСТВО. Равенство докажем методом математической индукции. Если и = 1, по определению, [Го,тг] = [го, [8Ы]]. Предположим, что утверждение теоремы выполняется при п = гп, т.е.
для любой цепной дроби (6о, Ь„...,6 [Ьо., Ьы Ьг,..., Ь,] = [6о, 6ы 6г,..., Ь, ы [Ьг", 6гьы..., Ь ]) для 1 < г' < гп. Рассмотрим п = и+ 1. Пусть (го ты1г,..., т .ь~] — цепная дробь и 1 < й < т + 1. Тогда (то,ты...,Х .ь~) = (го',(8г,тг,...,Г .ь~Ц (по определению) = = (10, '[11,12,...,Гь 1, [1Ытььъ ° ° ~ ~п ь1)]]~ полагая по индуктивному предположению Ь, = т,~~ и 1 = й — 1. Таким образом, [Го,'Гы",Г ьг[ = [1о',т~,тг,,ть-ы[1ь,'1ьчы.,Г ьг]] согласно определению цепной дроби. Следовательно, по методу индукции теорема справедлива. 310 ГЛАВА 7.
Теория чосел ° УПРАЖНЕНИЯ 1. Найдите два представления цепной дробью, [со,с1,...,с„], для каждого из приведенных ниже рациональных чисел: а) 37/11; б) 48/1003; в) -257/2003; г) 11/37; д) -5/44; е) 5. 2. Вычислите приведенные рациональные числа и выразите их в виде р/д, где р и о — целые числа: а) [3;5,2]; б) [О;3,5,2); в) [ — 10;1,4,3); г) [6; 4, 7, 3, 5]; д) [2;5,3]; е) [5;3,7,4,6]. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
