Дәрістер тезистері 1 тақырып Жиындар теориясының элементтері Мақсаты
жүктеу/скачать 2,42 Mb.
|
Дискретт математика. Дәрістер
- Бұл бет үшін навигация:
- . 185 және 5
| Евклид алгоритмі
Лемма 1. Егер , онда ( , ) = Дәлелдеуі: 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 болсын. Онда ( , )= ( , ) Евклид алгоритмін қолданамыз = + = + - - - - - - - - - - - - = + = ( , )= = ( , ) . . - және сандарының кез келген ортақ бөлгіші болсын, онда ( ; )= ( , )= ( ; )= ( ; ) жүктеу/скачать 2,42 Mb. Достарыңызбен бөлісу:
|