Evklid algoritmı


Eng kichik umumiy karrali (EKUK)


Download 308.5 Kb.
bet3/7
Sana09.03.2023
Hajmi308.5 Kb.
#1256051
1   2   3   4   5   6   7
Bog'liq
Evklid

3. Eng kichik umumiy karrali (EKUK)
Tariyp: a1, a2, a3, … , an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=255133, b=3274, c=53172 sanlardı bir apiwayı sanlar dárejeleriniń kóbeymesi formasında jazıń.
Sheshiliwi.
a=255133=25305170133170,
b= b=3274=20325074130170,
c=53172=20305370130172.

Download 308.5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling