Algebra Ipk, 12.03.12, tehtävä 1a

Laske syt(513,4199) Eukleideen algoritmin avulla ja esitä se muodossa 513x+4199y, missä x ja y ovat kokonaisia lukuja.

Tästä löytyy Eukleideen algoritmin interaktiivinen ohjelma.

Eli:

4199=513*8+95
513=95*5+38
95=38*2+19
38=19*2+0

Siis syt(4199,513)=19

Ja sitten takseenpäin:

19=95-38*2
38=513-95*5 => 19=95-(513-95*5)*2
95=4199-513*8 => 19=(4199-513*8)-(513-(4199-513*8)*5)*2

Sivotaan vähän:

(4199-513*8)-(513-(4199-513*8)*5)*2=11*4199-90*513

syt(4199,513)=19=11*4199-90*513

Ei ole kovin mutkikasta, mutta silti olen ylpeä siitä – joskus lukiossa olin itse keksinyt tämä.. Tuntuu hyvältä ei olla tyhmempi kuin Eukleidi :mrgreen: