Suurim ühistegur

Naturaalarvude $a$ ja $b$ suurimaks ühisteguriks (SÜT) nimetatakse suurimat naturaalarvu $c$, millega jaguvad $a$ ja $b$ 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 $a$ ning arvu 0 suurimaks ühisteguriks arvu $a$ ennast, st SÜT(a, 0) = a. Arve, mille suurim ühistegur on 1, nimetatakse ühisteguriteta arvudeks. Mõnikord defineeritakse ka naturaalarvude $a_{1},a_{2},...,a_{n}$ suurim ühistegur: SÜT($a_{1},a_{2},...,a_{n}$) = SÜT(... SÜT(SÜT($a_{1},a_{2}$), $a_{3}$),$...,a_{n}$).

Tähistatakse $\operatorname {S{\ddot {U}}T} (a,b)=c$.

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 $\operatorname {S{\ddot {U}}T} ({a \over c},{b \over c})={\operatorname {S{\ddot {U}}T} (a,b) \over c}$.

• 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 $\operatorname {S{\ddot {U}}T} (b,c)={{bc} \over {\operatorname {V{\ddot {U}}K} (b,c)}}$.

• $\operatorname {S{\ddot {U}}T} (2^{a}-1,2^{b}-1)=2^{\operatorname {S{\ddot {U}}T} (a,b)}-1$.

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: $84=2\cdot 2\cdot 3\cdot 7$ ja $720=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5$. Kuna mõlemas korrutises on sees tegurid 2 · 2 ja 3, siis $\operatorname {S{\ddot {U}}T} (84,720)=2\cdot 2\cdot 3=12$.

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