Mavzu. Yevklid algoritmi. Ekub va ekuk ni 2 usul bilan topish

Mavzu. Yevklid algoritmi. EKUB va EKUK ni 2 usul bilan topish.
Ta’rif. Agar va butun sonlarning ikkisini ham bo’ladigan son shu sonning umumiy bo’luvchisi deyiladi.
Teorema. Har qanday va sonlar uchun yagona sonlar topiladiki,
tenglik o’rinli bo’ladi.
Ta’rif . Agar va natural sonlar umumiy bo’luvchilarining eng kattasi shu sonlarning eng katta umumiy bo’luvchisi (EKUB) deyiladi va ko’rinishda belgilanadi.
Ta’rif. Agar bo’lsa, u holda va natural sonlar o’zaro tub sonlar deyiladi.
Ta’rif. Agar bo’lsa, va bo’ladi.
Misol. Berilgan 125 va 244 sonlari o’zaro tub bulganligi uchun ,
Ta’rif. Agar va natural sonlarning har biriga qoldiqsiz bo’linvchu eng kichik natural songa va sonlarning EKUKi deyiladi va belgilanadi.
M: 1-USUL. Berilgan 24 va 36 sonlarini EKUB va EKUKini 2 usulda topamiz.

24 2 36 212 2 18 2

6 2 9 3
3 3 3 3
1 1


,
2-USUL. Berilgan sonlar uchun qoldiqli bo’lish teoremasi yordamida Evklid algoritmini tuzamiz.


Evklid algoritmidagi oxirgi noldan farqli qoldiq EKUBni beradi.
Demak, .
Bundan
Misollar.
Ikki usulda berilgan sonlarning EKUB va EKUK larini toping:
1. a = 1786 ; b = 705 . 12. a = 4373; b = 3281 .
2. a = -826 ; b = 822 . 13. a = 1068 ; b = 899 .
3. a = 3655 ; b = 1023 . 14. a = 31605 ; b = 498 .
4. a = 3059 ; b = 1352 . 15. a = 1518 ; b = 731 .
5. a = 2737 ; b = 1627 . 16. a = 2516 ; b = 3360 .
6. a = 1488 ; b = 1126 . 17. a = 9163 ; b = 22083 .
7. a = 9234 ; b = 6574 . 18. a = 294 ; b = 2048 .
8. a = 3928 ; b = 2937 . 19. a = 5473 ; b = 2739 .
9. a = 7362 ; b = 632 . 20. a = 3726 ; b = 27364 .

10. 
    a = 37261 ; b = 372 . 21. a = 8372 ; b = 3726 .
    
11. 
    a = 7261 ; b = 1372 . 22. a = 372 ; b = 726 .
    

va natural sonlarni toping :

1. 
   ; 6. ; 11. ;
   
2. 
   ; 7. ; 12. ;
   
3. 
   ; 8. ; 13. ;
   
4. 
   ; 9. ; 14. ;
   
5. 
   ; 10. ; 15. ;