ЕүОБ. Евклид алгоритмі. Екое. 3 анықтама
жүктеу/скачать 138,57 Kb.
|
РК2
- Бұл бет үшін навигация:
- анықтама .
- Евклид алгоритмі Лемма 1.
- . 185 және 5
|
ЕҮОБ. Евклид алгоритмі. ЕКОЕ. 3 анықтама. , ... , сандарының әрқайсысын да бөлетін 0 бүтін санын олардың ортақ бөлгіші деп аталады. 4 анықтама. Егер келесі екі шарт орындалса: бүтін саны , ... , сандарының ортақ бөлгіші болса; , ... , сандарының кез-келген ортақ бөлгішіне бөлінсе; онда бүтін саны осы сандардың ең үлкен ортақ бөлгіші деп аталады. Қысқаша ЕҮОБ және = (, ... , ) деп белгіленеді. және сандары үшін (,) = .
Дәлелдеуі: 1) и - және ортақ бөлгіші. 2) - және ортақ бөлгіші болсын. , (,) = . Лемма 2. Егер =+, мұндағы a,b, нөлден өзгеше сандар, онда (,) = (, ). Евклид алгоритмі екі санның ЕҮОБ табу үшін қолданылады. және - оң сандар болсын, >>0. Алдымен санын санына бөлеміз, егер -ға бөлінсе, онда 1 лемма бойынша , ал егер -ға бөлінбесе, онда қалдықпен бөлу теоремасы бойынша қалдық аламыз: =+, 0<. . =0, яғни =. . 0, онда келесі теңдіктерді аламыз. =+; 0 < < (егер =0, онда процесс аяқталады). =+ 0<< - - - - - - - - - - - - - - - - - - - - - - (I) =+ 0<< = Біз =0 алған кезде бұл процесс аяқталады. Бөлу процесінде шыққан сандар натурал болғандықтан және кемімелі болғандықтан, қандай-да бір қадамда қалдықсыз бөлу аламыз. 2 лемма бойынша: (, ) = (,) = (,) = …= (,) = . Қорытынды: Ең соңғы нөлден өзгеше қалдық а және в сандарының ЕҮОБ болып табылады. Мысал. 185 және 5 сандарының ЕҮОБ табу керек. (185, 55)= 5. , ... , сандар жиынының ЕҮОБ табу есебі екі санның ЕҮОБ табу болып табылады.. 1 теорема. Егер (, )= ; (, )= , … , (, )= , онда (, ... , )=. ЕҮОБ қасиеттері. . 0, Z болсын. Онда (, )= (, ) Евклид алгоритмін қолданамыз = + = + - - - - - - - - - - - - = + = (, )= = (, ) . . - және сандарының кез келген ортақ бөлгіші болсын, онда (; )= (, )= (; )= (; )
жүктеу/скачать 138,57 Kb. Достарыңызбен бөлісу:
|