Geddes, Czapor, Ladahn - Algorithms for Computer Algebra (523146), страница 64
Текст из файла (страница 64)
рог ехашр1е, Н Е = 2, д = 5, апд т) = !00 ш йе аЬоче погадап йеп йе !пгебегв ш111 8готч го арргохипаге!у 50 д!8!гв тп !еп8й. Бо!ч!п8 висЬ а ргоЫеш Ьу йе шейод оЕ гЫв весдоп и ои!д Ье те1адчЫу гпйа1 оп сопчепгюпа! вуьгешв. 1п гдеш оЕ йе аЬоче тешат)гв оп йе 8гошй |п йе вйе оЕ йе 1пте8егв, Ь !в ипроггапг го сЬоове йе еча1иадоп ро1пг геавопаЫу вшаН аг еасЬ вга8е оЕ йе гасить!оп.
1п рагдси!яг, тче чл!1 пот сЬоове а вшпдшд иррег Ьоипд [11) оп йе в[хе оЕ йе соеЕЕтс(епгв йаг сап арреаг 1п йе Еассогв ав пдВЬг Ье ипр!!ед Ьу ТЬеогеш 7.7. Оиг Ьеипвис а18оддип Ы я[!очтед го Ьаче коше ргоЬаЬг!пу оЕ та!ше, апд йе оп1у еввепда1 сопд!поп и йаг йе д!ч!в!оп сЬес1гв оЕ ТЬеогетп 7.7 пшвг Ье 8иагапшед го г1егесг 1псоттесг теьи1ьп Яо ие роке йе г[иевдоп: "Нотч вша(1 сап тче сЬоояе йе еча1иаиоп ро!пг Е апд уег Ье 8иашпгеед йаг д!ч)ь!оп сЬес[гв аге киЕЕгстепг го г[егесг шсопесг геьтдгв7" Езашр!е 7.21.
Коррова и е Ьаче А (х) = хь — 9хт — х ь- 9 = (х + 1) (х — 9) (х — 1), В(х) = х — Зх — 9 = (х + 1) (х — 9). 1Е ше сЬоове йе еча1иадоп ро!пс 9= !0, йеп ф„го(а)=99, ф„го(Ь)=11, апд у= !8сд(99,11) = 11. ТЬе 1О-ад!с тергевепгагюп оЕ 11 Ь в(гпр!у (х!О+ 1 апг[ йеге(оге С =х+1 И сошригед ав йе ргоровед РСР(А,В). Ро!п8 тбчйюп сЬес1гв, ше Впд йаг Р [А апг1 б [В. Ночечег, 0 Н пот йе сотгесг апвччег Ьиг(ь оп)у а Еасгог о( гЬе тгие РСР, УчтЬаг Ьав Ьаррепет[ Н йаг йе Еасгог О =х — 9 Ьая д!варреагед ипдег йе шаррш8 ь!псе ф, 10 (н) = 1.
ТЬеогепт 7.8 ргочев йаг д[ч[в1оп сЬес1гв аге 8ишапгеед го де!ест !псописг геви1гв ав !оп8 ав йе еча!иадап ропп и сЬовеп го Ье вшсду 8теагег йап 1+ пйп([А[„,[В[„). (Ечоге йш !и Ехашр!е 721, Е, = 1 + пип([А[„,[В[„), МнсЬ!в пот а тгт!сг Ьоипг1) ТЫя Н а 11Ые чса)гет гет[ийепшпг йал ТЬеогеш 7.7 ь!псе ше по 1оп8ег пеед го г1еа[ эпЬ (Ье попп оЕ еасЬ роквдЫе Еасгог аЕА апд В. Ягвг, что пеед йе Ео1!ачлп8 1епипа деа11п8 чт!гЬ йе в!те оЕ йе ! асгогв оЕ а ро! упопда! ччЬеп еча[иашд аг ап иие8ег ча1ие.
1.епипа 7.5. Еег Р и Х[хг,хт,...,хт[ Ье а поп-сопвтии ро!упопда1 1п опе ог птоге чап'- ,й!ея апд 1ег бе Х Ье а Ьдчеп ров!йче !пге8ег, ).ег х депосе опе о(йе чаггаЫеь х апд 1ег и и Х Ье ап гпге8ег ваикЕуш8 (743) [як[лЯ„+б+ !. И (> е Х[х!,~ ...тт ! Ь а иоп-сшш!ап! ро!упшпш! чюЬ йв! А!аопйпи (ог Сошримг А1аеЬга 325 Д(Р апс! ф ~Я)е Х (7А4) йеп 1фч-и ((2)1 (7.45) Ргооу! Риз! сопвгбег йе ип!чапа!с сазе з. = 1. ).ес йе сопср1есе Гассопгасюп о( Р очег йе сошр1ех (!е!с) С Ье Р=сП(х-г) ! ! гог г; и С, чгЬеге с( < 1 !в йе с)евсее о1 Р апб с и 0 сз йе !еа41па сои!С)с(епс ог" Р. ТЬеп Ьу СаисЬу'в !пес!иа(1су, !РАЙ !г!) <1+ —. ~с) Рог апу а и Х ее Ьаче Ь(осч 1г" сс вапвбев (7.43) йеп гог еасЬ 1, ! ! а! -'! г, ~ ~ > (1+1 Р1„+б) -(1+ ) > б 1Р1 (и Ьеге гче Ьаче овес) йе !асс йас ~ с ~ Ь 1) у1е!обпд 1ф„и (Р)~ > ! с( бз ь б. (7.47) Б!ш1!аг1у, апу поп-сопзсапс ро1упоппа! Д и Х(х! запв(у!па (7.44) Ьав а (ассопгабоп очег С сопгбвбпб оГ опе ог пюге ог" йе !шеаг Гас!о!в !п (7.46) апс) йегесоге (7.47) ппрбев !ф ((44- >б ав с)а!пюсс.
Тига!па со йе ши!пчаг!асе саве /с > 1, чге сап сбоозе ча)иев а; о Х (!иу) (ог а11 чапаЫез к! ехсерс х = х -, висЬ йас !г" Ь(ош йас й!в сап а!счауз Ье асЬ)ечег( Ьу споивши йе ча1иез а! и Х агЬ!паг!1у !агае апс( агбссгап!у дсвсапс ггош еасЬ ойег. Ьгосч !г" С'С и Х(хсдг,...,хс) !з а поп-сопзшпс ро!упо- пиа1 вапв(у!па (744) йеп ф! (д) ( РС!) апс! йеге(оге, Ьу йе ип)чапа!с сазе а! аеас)у ргочесс, 1= <х,-ас,...,х,,-а; пх,+с-а,+и...,х„-аг> с(епосез йе !геше! ог" сЬе со!те!росс!!па еча1иабоп ЬопюпюгрЫвш йеп РС!) = ф! (Р) й а ишчапасе ро1упопиа! 1п х вабзГу1пд ! (Ъ И„.
327 7. Ро! упопиа[ СС0 Соптротаиоп 1Ф. о (Ф! (О))1- > 1Р61- а!Р1-. В и! Ф (Фт (О)) = Фт (ф. (О)) = Ф. (О) апсе йе огт[ег В иге1ечапт ]п йе арр11сабоп ог еча]иабоп ЬопюпютрЫяпв, апс$ Ьу (7.45), во йе ргоот !з соптр!ете. ТЬеогепт 7.8. [.ет А, В и Е[хт,х>...,хв[ Ье попхего ро1упопт[а[з ап6 1ет 8 и Х Ье а роя- 6че оие8ег забв(у!п8 8, > 1+ пап(1А1,1В1 ). ).ет у= СС0(а,[3) чгЬеге а = ф ((а) ап6 [3 = ф т (Ь), ап6 1ет С 6епоте йе ро!упопйв1 Еоппе6 ггопт йе 8;а6[с ехрапвюп о17 висЬ йат ф ~(б)=у.
С Ы а 8геатезт сопипоп 6!чЬог от" А ап6 В И вл6 оп1у В С[А ап6 С [ В. Ргоот: ТЬе (пвт Ьа!1 о( йе ргоо( о( ТЬеогегп 7,8 гепа!пз ча86 тот ТЬеогегп 7.7, у[е16- [п8 йе сопс1ияоп йат С = б Н тчЬеге ф„т (Н) =+1. Хобп8 йат Н [в а застиг от" А ап6 от" В, 1ет Р 6епоте йе ро! упопба! А ог В илтЬ пйпппипт попп. ТЬе сопг86опв ог" 1.епипа 7.5 аге ва6вйет[ Еог Р чг!1Ь х = х„, св = Ц, ап6 8 = 1, вп6 йегетоге Н Н !з в поп-сопявлт ро1упогпта1 чче Ьаче [Ф (н)1> ! соптгагВс6п8 йе аЬоче сопс!ияоп. ЧЪив Н пивт Ье а сопвтапт, чгЬепсе Н =х], ргоч1п8 йат б Ы ап авзос!ате от" 8.
ТЬе Неигвбс СС0 А!8ог!6ип ТЬеогегп 7.8 р!асев а !отчет Ьоипд оп йе яхе от" йе еча!иабоп роют тчЫсЬ 8ивгвптеев гссо8пЬюп от" !псопест геви1тв Ьу 61чп8оп сЬес[тв. Нои ечег, тЬеге ех!я ргоЫетпз тчЬеге тЫв ирргоасЬ 86!в то Впд йе тгие СС0 ч!а йе г„-а6!с ехрапвюп птейо6, по тпаиег чгЬат еча1иа6оп ро!пт Н изе6. %е почч члвЬ то сопест йе а18опйтп зо йатйеге тч61 аЬчаув Ье а геавопаЫе ргоЬаЫ!!ту о( васоева тот апу ргоЫепт. Ехаптр!е 7,22. Биррове йат А(х)=х — Зх +2х =(х-2)(х — 1)х В(х) = к + 6хт+! 1х+6=(х+ 1] (х+ 2) (х+ 3) в]ото йи йе попив агс 8!чеп Ьу1А1 = 3 ап6181 = !1. Ву '!Ъсогсгп 7.8 тче сап сЬоове 328 А18опйии тот Согпршег А!ПеЬга «=5. %е8етф„я(А)=60,ф я(В)=336,апт!у=!Пот!(60,336)=12.
ТЬе«-ат)!сгергевеитатюп от" 12 1з 2х5+ 2 апт1 тЬегеГоге б(х) = 2х+2 тз сошрпеед ак йе ргорояег) бСР(А,В). От" соотве йе ипе бСР !з 1 апд т)!ч!в!оп сЬес1тв аАП г(етест йат й!з гевпЬ (з шсогтесс Тгу!п8 а яесоид Пгие, тч!й а 1аг8ег ечз1иаПоп ро)иг, вау « = 20, »че Пег ф* — то (А) = 6840* ф» то (В) = 10626, апт! 7= !8ст!(684010626) =6. ТЬе «асс гергеяептаПоп от" 6!в 6 штт( йегетоге б = 6 Е сошрогег! ав йе ргорояетт бСР(А,В).
А8аш йе йч1- я!ап сЬес)гк т»П! т!етест йат 6 гк иот а тасюг о! йе ог!ЬПпа1 ро!упопиа!я. ТЬпв П тче втор аттег ьчо ечаЬшПопз тче шП! гетшп йе аиячгег 661 тот й)я ехашр!е. 1п йе саве ат" Ехаир)е 7.22, йе ро!упоппа)з А апг! В «оП а)тчауз Ьаче а сопшюп гас!от, чтЬеп еча)иатег), о( ат 1еаы 6. %Ьеп а вшаП еча1иаПоп ро!пт !з сЬовеи, аз аЬоче, йеп йтз ехпапеоив штезет !асюг мпП Ье шшгро!атея! то ап ехтгапеопв ро1упопйа( !астог, уте!дш8 ап шсопест тези!т. Ечеп !т" йе еча1иапои ропп Е яиП)с)еиПу!яг8е йеп апу ехпаиеопя !пте8ег васют ичП гептшп ав ап 1пте8ег сои!сит !и йе !птетро)атет) ро1упопиа1.
%е ате йеге(ого!ет) то тЬе сопсерт о! гепюч)п8 йе 1пте8ег соптепт ттош йе ро!упопих а1я. %е тчП! йеге(оге 1шрозе йе сопПгюп йат йе! ирш ро1упопаа! я А апт$ В зге рптЬфче чАй тезрест то Х йат 1я, тЬе ште8ег соптепт Ьаз Ьееп гетпочет! !гоги А апг) тгош В. СопезропсПп8!у, тче чтП! теточе йе ште8ег сопгепт тгош йе сошрптег! ро!упопйа1 б Ье(оте тета Йч!т)ш8 Ьесаияе йе г))ч)котя о! а рг1ппПче ро1уиопйа1 шпзт Ье ргипигче ( сЕ Ехегс1ве 7.4 ). Ь]отч )т Ьесошез сгисиП тот из то епвоге йат»чЬеп что гепюче йе 1ите8ег сои!сит гтош б ъче аге пот гешочш8 аиу гас!ига йат сопеяропг( то !зстогз о! йе пие ОСР С. рог 1! а Гас!от о( С еча!пагея то аи ште8ег йат !я зшзП ге1апче то «(ярес16саПу, 1еяк йзл «/2) йеп зисЬ ап 1пте8ег шау гепаш ав рагс о( йе !пте8ег сои!сит 1и йе шштроЫед ро!упопйа1 апт) чАП Ье дисагдей %е аге йеп Ьас1с ю йе я!шаПои тчЬеге йе гПч!Поп сЬесЬв пшу засосет! ечеп тЬои8Ь йе сошришд б !з пот а Пгеашзт сопипои гПч(вот. ТЬеогеги 79 йошв Ьотч 1аг8е тче плат иочг сЬоове «яо йат, ечеп тчЬеп йе )пте8ег соптеит ! в гепюче»1, йе тПчыюи сЬес)г тч)П 8!че а пие апятчег.
ТЬеотеш 79. (лт А, В и Х(хтхь...,х] Ье поптего Ро!Упопйа1в и ЬкЬ аге РгшППче чий теярест со Х. (ет «и Х Ье а роППче !пте8ег яат!ягу)п8 «) 1+2 пйп(]А] ]В~ ). (7.48) 1.ет у=бСР(п,р) шЬеге а =ф 4(А) аит! ]3 =ф ~(В), аиг)1ет б т)епоте йе ро!уиопйа1 гоииет! (гош йе «ат(!с ехраиз!ои от 7 апт! валят)4п8 фл-т (б) =Х %11Ь рр(б) деиопп8 йе тези)т о! ПиАгПп8 б Ьу !ь ште8ег сои!сит, рр(б) = бСР(А,В) П штт! оп!у !т рр(б)] А апт) рр(б)] В. 7. Ро!упопйа1 ОСР Согпригабоп 329 Ргоой Ргосеед1п8 ав )п йе Епкг Ьа!Е оЕ йе ргооГ оЕ ТЬеогепт 7.7, иге 1ег С = СтСР(А,И) апг1 иге сап сопс!ибе йаг С = рр(Сг) Н гчЛеге Фл 4(РР(б)) Фя 4(Н)17 ЛГоит 1Е что 6епоге йе !гребет сопгспг оЕ С Ьу к йеп рр(С) = Оlх ко кче Лаче -~.
Ф;-4 (н)! т. ЛГи!6Р1У)п8 йтои8Л ЬУ к У1е16к фл г (Н) ~ к Егогп ччЫсЬ чте сопс!ибе ГЬат фл 4(Н) и Х ап6 Гшйеппоте ! Фл 4 (Н) ) < К < $',Гк, (7.49) Е /2 > 1 +~ Р'$ ТЛегеГоге, ГЕ Н Гк а поп-сопвгапг ро!упопиа1 чте Ьаче соппа61сг)п8 (7.49). ТЬив Н пик! Ье а сопкгаш, ччЬепсе Н = 61 Ьесаике С Гк рг!пибче, ргочтп8 йагрр(0) Гк ап аквос)аге оГ С. 9(те аге поки геабу го ртевепс а)8опбип РСРНЕ($. ТЬе а18опйгп аввшпев йаг йе !при! ро1упопиа!к аге рппипче апб йаг йе 1псе8ег соптепг кч$11 Ье тегпоче6 Гготп йе ошрш тешгпей 1$ авек йе геяй оЕ ТЬеогегп 7.9 1п сЛоояп8 йе еча1иабоп ро)пгв во йаг йе 61ч1- 6оп сЬес$гз сопкбитге а ча1гб сЛес)6п8 гпесЛап)вш.
ТЬе 6$ч1в!оп сЛес)гз Ье)п8 ике6 Гп ГЛе а$8опйгп ате Ьакеб оп обч1яоп оГ ро!упопйа!к очег йе Ве!6 оЕтанола! литЬеш, кч)6сЛ тк гишча1епт то гегпоч)п8 йе Гпге8ег сопгепг Египт йе 6!ч!вот аль йеп 6о)п8 сея 6$ч(к)оп очег йе Гпге8егк (побп8 йаг йе 61ч)6еп6 Гз а$геат)у рппйпче). То епкиге йаг йе са!си1а6оп 6оек пот Ьесопге гоо ехрепяче (Ь Гк оп1у а Леипкбс аЕгег аИ) кче сЛес$с оп йе яае оЕ йе Гпгебегв йаг чтои$6 Ье 8епегагед ГЕ йе сотпригатгоп кчеге а$)огче6 то ргссеп), ап6 йе ге!ига тпесЬапйпт тп йе а18опйгп ии 1п йй саве, Гпйсаге6 Ьу Когито То Тор !.ече1. ТЫк пеегЬ го Ье а слоге "дгакбс" гегшп пгесЛап1кгп йап йе шд1- пагу тейгпз арреапп8 ойегчлке Гп йе а18опйгп Ьесаиве оГ йе тесигвгче пасите оЕ йе а18о|пЛ~п ап6 йе Гас! йаг йеге гк по ропы !п сопг(пгбп8 сопгршабоп оп а ргоЫетп йаг Ьав 1еаб «кисЛ )ат8е 'птевегк.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
