Teksti

68=12*5+8
jaettavan ja jakajan suurin yhteinen tekijä on sama kuin jakajan ja jakojäännöksen

jakoyhtälössä a=nq+r
syt(a,n) = syt(n,r)

Esim. Määritetään Eukleideen algoritmin avulla syt(120,84)

Jaetaan luku 120 luvulla 84

$120=84\cdot1+36$

syt(120,84)=syt(84,36)

Jaetaan seuraavaksi 84 luvulla 36

$84=36\cdot2+12$

syt(84,36)=syt(36,12)

Jaetaan seuraavaksi 36 luvulla 12

$36=12\cdot3+0$

syt(36,12)=12

syt(120,84)=syt(84,36)=syt(36,12)=12

Kokonaislukuyhtälöt

$17x+14y=4$
$x_0=20$

$y_0=-24$

$syt\left(17{,}14\right)=1$

$x=20+\frac{14n}{1}=20+14n$
$y=-24-\frac{17n}{1}=-24-17n$

mikä tahansa kokonaisluku n paikalla toimii