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