Evklid algoritmı

3. Eng kichik umumiy karrali (EKUK)
Tariyp: a₁, a₂, a₃, … , a_nZ sanlardıń hár birine bólinetuǵın san bul sanlardıń ulıwma eseligi (bóliniwshisi) dep ataladı. Berilgen sanlardıń qálegen ulıwma eseligining bóliwshisi bolǵan ulıwma eseligi bul sanlardıń eń kishi ulıwma eseligi dep ataladı.
Berilgen sanlardıń eń kishi ulıwma eseligi h=EKUK (a, b) sıyaqlı belgilenedi.
Teorema. Eger d=EKUB (a, b), d≠0 bolsa, ol halda h=EKUK(a,b)= boladı.
Isbat: h sanı a hám b sanlarınıń ulıwma eseligi bolǵanı ushın va boladı.
X — a hám b sanlarınıń qálegen basqa bir ulıwma eseligi bolsın, ol halda x=au, x=bv (ol, vZ) boladı. Bunnan au=bv kelip shıǵadı. Bul teńliktiń hár eki tarepin d ǵa bólsek: . va sanlar óz-ara apiwayı bolǵanı ushın ol sanı ǵa bólinedi. Sonıń ushin , tZ. Bunnan, . Sonday qılıp, x doni ǵa bólinedi. Demek, x sanı h ǵa hám bólinedi.
Misol. EKUK(462,252) di tabıń.
462 = 252⋅1 + 210,
252 = 210⋅1 + 42,
210 = 42⋅5.
demek, EKUB(462,252) =42

Juwap: EKUK(462,252)=2772


Esaplar.
Tómendegi sanlardıń EKUK nı tabıń.
1) 645 и 381; 2) 846 и 246; 3) 5338 и 11618.
Juwap: 1) 81915; 2) 34686; 3) 197506.


4. Natural sanlardı apiwayı kóbeytiwshilerge ajıratıw.
Qálegen natural sandı apiwayı kóbeytiwshiler kóbeymesi formasında súwretlew múmkin, bunda birdey kóbeytiwshiler kóbeymesi dáreje formasında jazıldı. Eger zárúr bolsa, bul kóbeytiwde apiwayı sanlardıń nol kórsekishli dárejesin de qóllaw múmkin. Sonday etilgende shekli sandaǵı qálegen apiwayı sanlardı birdey apiwayı sanlar oń pútkil kórsetkishli dárejeleriniń kóbeymesi formasında súwretlew múmkin.
Mısal. a=2⁵513³, b=3²7⁴, c=5³17² sanlardı bir apiwayı sanlar dárejeleriniń kóbeymesi formasında jazıń.
Sheshiliwi.
a=2⁵513³=2⁵3⁰5¹7⁰13³17⁰,
b= b=3²7⁴=2⁰3²5⁰7⁴13⁰17⁰,
c=5³17²=2⁰3⁰5³7⁰13⁰17².