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