1-amaliy mashg'ulot. Sonlarni ekubini hisoblash algoritmlari. Evklid algoritmi. Reja: Evklid algoritmi

1-amaliy mashg'ulot. Sonlarni EKUBini hisoblash algoritmlari. Evklid algoritmi.
Reja:

1. 
   Evklid algoritmi.
   
2. 
   Kengaytirilgan evklid algoritmi.
   

Evklid algoritmi.

1. 
   a, b a==b EKUB(a, b) = a || b
   
2. 
   a, b a!=b a > b a = b*q₁ + r₁, 0  r₁ < b, agar r₁=0 bo‘lsa, EKUB(a,b) = b, aks holda r₁!=0
   
3. 
   b = r₁*q₂ +r₂ 0  r₂ < r₁, agar r₂ = 0 bo‘lsa, EKUB(a,b)=r₁, aks holda r₂!=0
   
4. 
   r₁ = r₂*q₃ + r₃ 0  r₃ < r₂, r₃ = 0, EKUB(a,b)=r₂
   

r₃!=0
…… r_k = 0 EKUB(a, b) = r_k-1
Kengaytirilgan evklid algoritmi.
a, b natural sonlar uchun d = EKUB(a, b)
a + b = d,  berilgan sonlarning oldidagi koefitsenti

1. 
   qadam
   

1. 
   a = b*q₁ + r₁,
   
2. 
   b = r₁*q₂ +r₂,
   
3. 
   r₁ = r₂*q₃ + r₃,
   

2. 
   qadam
   

1. 
   a = b*q₁ + r₁, a - b*q₁ = r₁
   
2. 
   b = r₁*q₂ +r₂, b - r₁*q₂ = r₂
   
3. 
   r₁ = r₂*q₃ + r₃, r₁ - r₂*q₃ = r₃
   

2. 
   qadam.
   

r₃ = r₁ - r₂*q₃ = r₁ – (b - r₁*q₂) * q₃ = r₁ – b * q₃ + r₁*q₂*q₃ = r₁*(1 + q₂*q₃) – b * q₃ = (a – b * q₁)*( 1 + q₂*q₃) – b * q₃ = a*(1 + q₂*q₃)-b*q₁-b*q₁*q₂*q₃-b*q₃= >
a*(1 + q₂*q₃)-b*(q₁+q₁*q₂*q₃+q₃) = d.
1 + q₂*q₃, q₁+q₁*q₂*q₃+q₃

1-misol

453, 17 berilgan natural sonlar bo‘lsin. Bu sonlarni ENG KATTA UMUMIY BO ‘LUVCHISI (EKUB)ni topish kerak bo‘lsin, bunda Evklid algoritmidan foydalanamiz.

1. 
   Qadam.
   

1. 
   453 = 17 26 + 11
   
2. 
   17 = 11 
   
3. 
   
   
4. 
   
   
5. 
   qoldiq 0 bo‘lganligi sabab Evklid algoritmga ko‘ra EKUB (453, 17) = 1 bo‘lishini ko‘ramiz.
   

2-misol
453, 17 berilgan natural sonlar bo‘lsin. Bu sonlarni oldidagi koefitsentini toping.

1. 
   qadam
   

1. 
   453 = 17 26 + 11
   
2. 
   17 = 11 
   
3. 
   
   
4. 
   
   

 

2. 
   qadam
   

1. 
   453 = 17 26 + 11, 11
   
2. 
   17 = 11  
   
3. 
    
   
4. 
    
   

3. 
   Qadam
   



2-amaliy mashg'ulot. Sonlarni EKUBini Pythonda hisoblashning Evklid algoritmi dasturi