| Евклид алгоритмі.
Жоғарғы ЕҮОБ анықтамасынан кез келген ақырлы бүтін сандардың ЕҮОБ табылатыны шықпайды. Бұл сұраққа Евклид алгоритмі көмегімен жауап беруге болады. Ол төменгі екі леммаға көзделген:
1-Лемма. Егер , онда
2-Лемма. Егер , онда
2-теорема. Егер
Онда
Мысал. (2585,7975)=55
ЕҮОБ қасиеттері
3-теорема. Егер және онда .
4-теорема. бүтін сандарының шамасы бойынша ең үлкен оң ортақ бөлгіші осы сандардың ЕҮОБ болады.
5-теорема.
6-теорема. Егер , онда
Анықтама. теңдігі ЕҮОБ-тің а мен b сандарының сызықтық комбинациясы ретінде көрсетілуі деп аталады.
Мысал. ЕҮОБ(90,35)-тің сызықтық көрсетілуі : 5=2*90+(-5)*35 болып табылады.
Достарыңызбен бөлісу: | 
