Eukleideen algoritmi

Jakoyhtälössä a = nq + r

syt(a, n) = syt(n, r)

joten lukujen a ja n syt saadaan, kun toistetaan jakoyhtälöä, kunnes jakojäännös on 0. Syt on viimeinen nollasta eroava jakojäännös.
Tämä on nimeltään Eukleideen algoritmi.

ESIM. Selvitä lukujen 433 ja 38 suurin yhteinen tekijä jakoyhtälön avulla.

$433:38=11{,}39...$

$433-11\cdot38=15$

joten jakoyhtälö on:

$433=11\cdot38+15$

$38=2\cdot15+8$
$15=1\cdot8+7$
$8=1\cdot7+1$ <-- viimeinen nollasta eroava jakojäännös on syt
$7=7\cdot1+0$

joten syt( 433, 38 ) = 1

ESIM 1. Mikä on lukujen 343 ja 63 suurin yhteinen tekijä?

$343=5\cdot63+28$

$63=2\cdot28+7$
$28=4\cdot7+0$

Siis syt(343, 63) = 7.

Pyj saadaan kaavasta $a\cdot b=\text{syt}\left(a{,}b\right)\cdot\text{pyj}\left(a{,}b\right)$ eli
$\text{pyj}\left(a{,}b\right)=\frac{a\cdot b}{\text{syt}\left(a{,}b\right)}$ .

ESIM 2. Mikä on lukujen 14 ja 6 pienin yhteinen monikerta?

***

Tehtäviä
149, 150, 151, 156, 152, 155, 165a