Evklid algoritmi

2. Eng katta umumiy bo`luvchi (EKUB)
Ta`rif: a₁,a₂,a₃,…,a_nZ sonlarning umumiy bo`luvchisi deb, berilgan sonlarning har biri bo`linadigan dZ songa aytiladi.
Berilgan sonlarning umumiy bo`luvchi shu sonlarning barcha umumiy bo`luvchilariga bo`linsa, bu umumiy bo`luvchi berilgan sonlarning eng katta umumiy bo`luvchi deyiladi.
Berilgan sonlarning eng katta umumiy bo`luvchisi EKUB(a₁,a₂,a₃,…,a_n) kabi belgilanadi.
Eng katta umumiy bo`luvchining ta`rifidan ushbu muhim xossa kelib chiqadi:

1. 
   • agar d=EKUB(a₁,a₂,a₃,…,a_n) bo`lsa, a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, … , a<sub>n</sub> sonlarning barcha umumiy bo`luvchilari to`plami d sonining barcha bo`luvchilaridan iborat bo`ladi.
   
2. 
   • agar d=EKUB(a₁,a₂,a₃,…,a_n) bo`lsa, u holda d=EKUB(a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,…,a<sub>n</sub>,0) bo`ladi. Aksincha, agar d=EKUB(a₁,a₂,a₃,…,a_n,0) bo`lsa, d=EKUB(a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,…,a<sub>n</sub>) bo`ladi.
   

Agar EKUB(a₁,a₂,a₃,…,a_n)=1 bo`lsa, a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, … , a<sub>n</sub> sonlar “o`zaro tub sonlar” deyiladi.
Endi berilgan sonlarning eng katta bo`luvchisini qanday topish mumkinligi haqida fikr yuritamiz.
a,bZ, a ≠ 0, b ≠ 0 sonlar uchun: c<sub>1</sub>, c<sub>2</sub>, c<sub>3</sub>, …, c<sub>n-1</sub>, c<sub>n</sub> ketma-ketlikni quyidagi tuzamiz:
c<sub>1</sub>=a, c<sub>2</sub>=b deb olamiz. Agar bo`lsa, EKUB(a,b)=b bo`ladi. Aks holda c<sub>1</sub> ni c<sub>2</sub> ga bo`lishda hosil bo`lgan qoldiqni c<sub>3</sub> deb olamiz, c<sub>2</sub> ni c<sub>3</sub> ga bo`lishdagi qoldiqni c₄ deb olamiz va hokazo.
Bunday qoldiqli bo`lishlar ketma-ketligini qulaylik uchun tengliklar zanjiri ko`rinishida bunday yozamiz:
c₁=c₂q₂+c₃
c₂=c₃q₃+c₄
c₃=c₄q₄+c₅
…………
c_n-2=c_n-1q_n-1+c_n
c_n-1=c_nq_n

qoldiqli bo`lish natijasida qoldiqlar uchun c<sub>2</sub>>c<sub>3</sub>>c<sub>4</sub>… munosabat o`rinli bo`ladi, bundan tashqari qoldiqlar nomanfiy sonlardir. Shu sababli bu qoldiqlar orasida nolga teng bo`ladigani albatta uchraydi. c_n uchun noldan farqli oxirgi qoldiqni olamiz. Bu holda c_n-1 soni c_n ga bo`linishi ravshan.

Hosil qilingan c₁, c₂, c₃, …, c_n-1, c_n ketma-ketlik a va b sonlari uchun Evklid ketma-ketligi deyiladi.
Ketma-ket qoldiqli bo`lish yordamida bunday ketma-ketlikni hosil qilish usuli Evklid algoritmi deb ataladi.
Misol. 78 va 24 sonlari uchun Evklid ketma-ketligini tuzing.
Yechilishi.
78=244+18
24=181+6
18=63+0
Bundan, izlangan ketma-ketlik hosil bo`ladi: 78, 24, 18, 6.
Теорема. a va b (a≠0,b≠0) sonlar uchun tuzilgan Evklid ketma-ketligi c₁, c₂, c₃, …, c_n-1, c_n ning oxirgi hadi a va b sonlarining eng katta umumiy bo`luvchisi bo`ladi: c_n=EKUB(a,b).
Isbot: c₁, c₂, c₃, …, c_n-1, c_n sonlar o`zaro yuqorida keltirilgan qoldiqli bo`lish munosabati bilan bog`langan. Tengliklar zanjiri orqali yuqoriga harakatlanib, quyidagilarni aniqlaymiz:
c<sub>n-1</sub>=c<sub>n</sub>q<sub>n</sub> munosabatdan ;
c<sub>n-2</sub>=c<sub>n-1</sub>q<sub>n-1</sub>+c<sub>n</sub> munosabatdan ;
c<sub>n-3</sub>=c<sub>n-2</sub>q<sub>n-2</sub>+c<sub>n-1</sub> munosabatdan ;
va hokazo
va .
Bunda c<sub>1</sub>=a va c<sub>2</sub>=b. Shunday qilib, c<sub>n</sub> — a va b sonlarining umumiy bo`luvchisi.
x soni a va b sonlarining boshqa bir umumiy bo`luvchisi bo`lsin. Evklid algoritmidagi qoldiqli bo`lishlar zanjirida pastga qarab harakatlanib, quyidagilarni aniqlaymiz:
c<sub>1</sub>=c<sub>2</sub>q<sub>2</sub>+c<sub>3</sub> ga teng kuchli c<sub>3=</sub>c<sub>1</sub>-c<sub>2</sub>q<sub>2</sub> munosabatdan
c<sub>2</sub>=c<sub>3</sub>q<sub>3</sub>+c<sub>4</sub> ga teng kuchli c<sub>4=</sub>c<sub>2</sub>-c<sub>3</sub>q<sub>3</sub> munosabatdan
mulohazalarni davom ettirib,
c<sub>n-2</sub>=c<sub>n-1</sub>q<sub>n-1</sub>+c<sub>n</sub> ga teng kuchli c<sub>n</sub>= c<sub>n-2</sub>-c<sub>n-1</sub>q<sub>n-1</sub> munosabatdan ga ega bo`lamiz.
Shunday qilib, ta`tifga ko`ra, c_n=EKUB(a,b).
Misol. EKUB(42598, 2014) ni toping.
Yechilishi. Berilgan sonlar uchun Evklid ketma-ketligini tuzamiz. Qoldiqli bo`lishlar ketma-ketligini quyidagi sxema bo`yicha bajarish qulay:

_42598  2014
4028 21
_ 2318
2014
_ 2014  304
1824 6
_ 304  190
190 1
_ 190114
114 1
_ 114  76
76 1
_ 76  38
76 2
0
Javob: EKUB(42598, 2014) = 38.


Mashqlar.
Evklid algoritmi yordamia quyidagi sonlarning EKUB ini toping:
1) 645 va 381; 2) 846 va 246; 3) 15283 va 10013; 4) 6188 va 4709 ;
5) 4005 va 2581.
Javob: 1) 3; 2) 6; 3) 527; 4) 17; 5) 89.


3. Eng kichik umumiy karrali (EKUK)
Ta`rif: a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, … , a<sub>n</sub>Z sonlarning har biriga bo`linadigan son bu sonlarning umumiy karralisi (bo`linuvchisi) deyiladi. Berilgan sonlarning istalgan umumiy karralisining bo`luvchisi bo`lgan umumiy karralisi bu sonlarning eng kichik umumiy karralisi deyiladi.
Berilgan sonlarning eng kichik umumiy karralisi h=EKUK(a,b) kabi belgilanadi.
Teorema. Agar d=EKUB(a,b), d≠0 bo`lsa, u holda h=EKUK(a,b)= bo`ladi.
Isbot: h soni a va b sonlarining umumiy karralisi bo`lgani uchun va bo`ladi.
x — a va b sonlarining istalgan boshqa bir umumiy karralisi bo`lsin, u holda x=au, x=bv (u,vZ) bo`ladi. Bundan au=bv kelib chiqadi. Bu tenglikning har ikki tomomini d ga bo`lsak: . va sonlar o`zaro tub bo`lgani uchun u soni ga bo`linadi. Shuning uchun , tZ. Bundan, . Shunday qilib, x doni ga bo`linadi. Demak, x soni h ga ham bo`linadi.