Mavzu: Yevklid algoritmi

Evklid algaritmi
1-qadam:
Ikkita natrul son tanlab olamiz a va b shu sonlar o‘zaro a=b teng bo‘lsa Evklid algaritmi EKUB(a,b)= a yoki b teng bo’ladi.
2-qadam:
Ikkita natural son mavjud a va b lekin bu sonlar a≠b bir biriga teng emas, a soni b sondan katta a>b bu holatda a ni b ga bo‘lamiz r₁ qoldiq son mavjud bo‘ldi a=bq₁+r₁ bu r₁ son 0dan katta yoki teng bo’lishi mumkin b dan kichik bo’ladi 0 r₁ agar r₁=0 bo‘lsa Evklid algaritmi uchun EKUB(a,b)=b b son EKUB hisoblanadi
3-qadam:
r₁ teng bo’lmasa
b ni qoldiqqa bo’lamiz b=r₁q₂+r₂ va yangi hosil bo’lgan r₂ 0 r_{2 1} tengsizlikga qo’yiladi agarda r₂=0 EKUB(a,b)=r₁
agar r₂ 0 shart davom etadi.
4-qadam:
r₁ ni r₂ bo‘lamiz r₁=r₂q₃+r₃ va yana 0 r_{3 2} r₃=0 EKUB(a,b)=r₂
agar r₃ 0 shart davom etadi.
…….. r_k=0 EKUB(a,b)=r_k-1

Misol:
453 17

1. 
   453>17 453=17*26+11
   
2. 
   17=11*1+6
   
3. 
   11=6*1+5
   
4. 
   6=5*1+1
   
5. 
   5=5+0 EKUB(453,17)=1
   

��−1=gcd(�,�).