Evklid algoritmı

2. Eń úlken ulıwma bóliwshi (EKUB)
Tariyp: a1, a2, a3, …, a_n ÎZ sanlardıń ulıwma bóliwshisi dep, berilgen sanlardıń hár biri bólinetuǵın dÎZ sanǵa aytıladı.
Berilgen sanlardıń ulıwma bóliwshi sol sanlardıń barlıq ulıwma bóliwshilerine bólinse, bul ulıwma bóliwshi berilgen sanlardıń eń úlken ulıwma bóliwshi dep ataladı.
Berilgen sanlardıń eń úlken ulıwma bóliwshisi EKUB (a1, a2, a3, …, an) sıyaqlı belgilenedi.
Eń úlken ulıwma bóliwshiniń tariypinen bul zárúrli qasiyet kelip shıǵadı :
• eger d=EKUB (a1, a2, a3, …, an) bolsa, a1, a2, a3, …, an sanlardıń barlıq ulıwma bóliwshileri kompleksi d sanınıń barlıq bóliwshilerinen ibarat boladı.
• eger d=EKUB (a1, a2, a3, …, an) bolsa, ol halda d=EKUB (a1, a2, a3, …, an, 0) boladı. Kerisinshe, eger d=EKUB (a1, a2, a3, …, an, 0) bolsa, d=EKUB (a1, a2, a3, …, an) boladı.
Eger EKUB (a1, a2, a3, …, an) =1 bolsa, a1, a2, a3, …, an sanlar “óz-ara apiwayı sanlar” dep ataladı.
Endi berilgen sanlardıń eń úlken bóliwshisin qanday tabıw múmkinligi haqqında pikir júrgizemiz.
a, bÎZ, a ≠ 0, b ≠ 0 sanlar ushın : c1, c2, c3, …, cn-1, cn izbe-izlikti tómendegishe dúzemiz:
c1=a, c2=b dep alamız. Eger bolsa, EKUB (a, b) =b boladı. Keri jaǵdayda c1 ni c2 ge bolıwda payda bolǵan qaldıqtı c3 dep alamız, c2 ni c3 ke bolıw daǵı qaldıqtı c4 dep alamız hám taǵı basqa.
Bunday qaldıqlı bólıwler izbe-izligin qolaylı bolıwı ushın teńlikler shınjırı kórinisinde bunday jazamız :
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

qaldıqlı bólıw nátiyjesinde qaldıqlar ushın c2>c3>c4… munasábet orınlı boladı, bunnan tısqarı qaldıqlar oń sanlar bolıp tabıladı. Usınıń sebebinen bul qaldıqlar arasında nólǵe teń bolatuǵını álbette ushraydı. c_n ushın nólden ayrıqsha aqırǵı qaldıqtı alamız.

Payda qılınǵan c₁, c₂, c₃, …, c_n-1, c_n izbe-izlik a hám b sanları ushın Evklid izbe-izligi dep ataladı.
Izbe-iz qaldıqlı bolıw járdeminde bunday izbe-izlikti payda etiw usılı Evklid algoritmı dep ataladı.
Mısal. 78 hám 24 sanları ushın Evklid izbe-izligin dúziń.
Sheshiliwi.
78=244+18
24=181+6
18=63+0
Bunnan, izlengen izbe-izlik payda boladı:
78, 24, 18, 6.
Teorema. a va b (a≠0,b≠0) sanlar ushin dúzilgen Evklid izbe-izligi c₁, c₂, c₃, …, c_n-1, c_n niń aqırǵı hadi a hám b sanlarınıń eń úlken ulıwma bóliwshisi boladı : cn=EKUB (a, b).
Dalill: c₁, c₂, c₃, …, c_n-1, c_n sanlar óz-ara joqarıda keltirilgen qaldıqlı bolıw munasábeti menen baylanısqan. Teńlikler shınjırı arqalı joqarıǵa háreketlenip, tómendegilerdi anıqlaymız:
c_n-1=c_nq_n munasábetten ;
c_n-2=c_n-1q_n-1+c_n munasábetten ;
c_n-3=c_n-2q_n-2+c_n-1 munasábetten ;
va hokazo
va .
Bunda c₁=a va c₂=b. Sonday qılıp, c_n — a hám b sanlarınıń ulıwma bóliwshisi.
x sanı a hám b sanlarınıń basqa bir ulıwma bóliwshisi bolsın. Evklid algoritmındaǵı qaldıqlı bolıwlar shınjırında tómenge qaray háreketlenip, tómendegilerdi anıqlaymız:
c₁=c₂q₂+c₃ ga teń kúshli c₃₌c₁-c₂q₂ munasábetten
c₂=c₃q₃+c₄ ga teń kúshli c₄₌c₂-c₃q₃ munasábetten
oy-pikirlerdi dawam ettirib,
c_n-2=c_n-1q_n-1+c_n ǵa teń kúshli c_n= c_n-2-c_n-1q_n-1 munasábetten ge iye bolamız.
Sonday etip, , cn=EKUB (a, b).
Mısal. EKUB (42598, 2014) ni tabıń.
Sheshiliwi. Berilgen sanlar ushın Evklid izbe-izligin dúzemiz. Qaldıqlı bólıwler izbe-izligin tómendegi sxema boyınsha orınlaw qolay :

_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
Juwap: EKUB(42598, 2014) = 38.

Shınıǵıwlar.

Evklid algoritmı járdeminde tómendegi sanlardıń EKUB ini tabıń :
1) 645 hám 381; 2) 846 hám 246 ; 3) 15283 hám 10013; 4) 6188 hám 4709 ;
5) 4005 hám 2581.
Juwap: 1) 3; 2) 6; 3) 527; 4) 17; 5) 89.