Diofantoksen

http://www.oph.fi/etalukio/opiskelumodulit/pimatem/paavalikko/pmku13/lukuteoria/9.html

Tarkastellaan ensin yleisen (ensimmäisen kertaluvun) Diofantoksen yhtälön ratkaisua:

ax by = c, (1)

missä a, b ja c ovat kokonaislukuvakioita. En tässä todista mitään, mutta kerron, että yhtälöllä (1) on ratkaisuja, jos ja vain jos syt(a,b) jakaa luvun c, eli syt(a,b)|c. Syt(a,b) saadaan määritettyä Eukleideen algoritmilla, jota (jos syt(a,b)|c) käänteisessä järjestyksessä soveltamalla saadaan yhtälölle yksi ratkaisu. Yleinen ratkaisu on tällöin muotoa

x = x_0 (b/syt(a,b))*t
y = y_0 - (a/syt(a,b))*t,

missä x_0 ja y_0 ovat edellä löydetty erikoisrakaisu ja t jokin kokonaisluku. No niin, sovelletaan sitten teoriaamme käytännön esimerkkiin, eli

5x - 3y = 1. (2)

Edellisin merkinnöin tässä a = 5, b = -3 ja c = 1. Toivon, että Eukleideen algoritmi on tuttu, muuten seuraava voi jäädä hieman hämäräksi - määritämme luvun syt(5,-3):

5 = (-1)*(-3) 2
-3 = (-2)*2 1
2 = 2*1 0,

eli syt(5,-3) = 1. Koska 1 jakaa luvun c = 1, on yhtälöllä (2) ratkaisuja. Sovelletaan sitten algoritmia toiseen suuntaan. Saamme

1 = -3 2*2 = -3 2*(5 - 3) = 2*5 3*(-3).

Siten yksi ratkaisu yhtälölle (2) on x_0 = 2, y_0 = 3. Yleinen ratkaisu on, kuten edellä totesimme

x = x_0 (b/syt(a,b))*t = 2 - 3t
y = y_0 - (a/syt(a,b))*t = 3 - 5t,

missä t on mikä hyvänsä kokonaisluku. Ratkaisun oikeellisuudesta on helppo varmistua kokeilemalla muutamaa t:n arvoa.

Helen