Suurim ühistegur

Naturaalarvude  ja  suurimaks ühisteguriks (SÜT) nimetatakse suurimat naturaalarvu , millega jaguvad  ja  nii, et jääki ei jää (st jääk on 0). Suurima ühisteguri mõistet on laiendatud ka täisarvudele ja polünoomidele.

Sageli loetakse suvalise naturaalarvu  ning arvu 0 suurimaks ühisteguriks arvu  ennast, st SÜT(a, 0) = a. Arve, mille suurim ühistegur on 1, nimetatakse ühisteguriteta arvudeks. Mõnikord defineeritakse ka naturaalarvude  suurim ühistegur: SÜT() = SÜT(... SÜT(SÜT(), ),).

Tähistatakse .

Näiteks SÜT(6, 14) = 2, sest suurim naturaalarv, millega 6 ja 14 jäägita jaguvad, on 2;  SÜT(9, 7) = 1; SÜT(6, 0) = 6.

Sageli laiendatakse suurima ühisteguri mõistet ka täisarvudele: suvaliste täisarvude a ja b suurimaks ühisteguriks nimetatakse nende arvude absoluutväärtuste suurimat ühistegurit, st SÜT(a, b) = SÜT(|a|, |b|).

Omadused

Olgu a, b, c, n, r naturaalarvud.

 SÜT(a, b) = SÜT(b, a).

 SÜT(na, nb) = n SÜT(a, b).

 Kui c on arvude a ja b ühistegur, siis .

 Kui SÜT(a, c) = 1, SÜT(b, c) = 1, siis ka SÜT(ab, c) = 1.

 Kui a on korrutise bc jagaja ja SÜT(a, b) = 1, siis a on c jagaja.

 Kui a on c jagaja ja b on c jagaja ning SÜT(a, b) = 1, siis korrutis ab on c jagaja.

 Kui r on jääk, mis tegib arvu a jagamisel arvuga b, siis SÜT(a, b) = SÜT(b, r).

 Olgu VÜK(b, c) arvude b ja c vähim ühiskordne, siis .

 .

Arvutamine
Levinud on kaks SÜT arvutamise viisi.

Leiame arvude a ja b kõik algtegurid (st algarvud, millega a ja b jaguvad jäägita). Leitud algteguritest eraldame SÜT arvutamiseks kõik need, mis on nii a kui ka b algteguriteks. Eraldatud algtegurid korrutame kokku.

Näiteks SÜT(84, 720) arvutamiseks:  ja . Kuna mõlemas korrutises on sees tegurid 2 · 2 ja 3, siis . 

Teine ja efektiivsem meetod on Eukleidese algoritm. Esimese sammuna leiame jäägi, mis tekib suurema arvu jagamisel väiksemaga. Järgmistel sammudel võtame eelmise sammu jagaja ning jagame teda jäägiga, mis eelmisel sammul leiti. Seda teeme nii kaua, kuni jäägiks saab null; siis esialgsete arvude SÜT on jagaja, millega jagamisel saadigi viimasel sammul jäägiks null.

Näiteks SÜT(84, 720) arvutamiseks: 720 / 84 = 8, jääk 48; 84 / 48 = 1, jääk 36; 48 / 36 = 1, jääk 12; 36 / 12 = 3, jääk 0. Seega SÜT(84, 720) = 12.

Vaata ka
Vähim ühiskordne

Välislingid
http://mathworld.wolfram.com/GreatestCommonDivisor.html

Aritmeetika