Esimerkki Diofantoksen yhtälön ja kongruenssin käytöstä

Esimerkki. Henkilö A osti tuotetta X hintaan 15e/kpl ja tuotetta Y hintaan 11e/kpl. Yhteensä hänen ostoksensa maksoivat 137e. Montako kappaletta hän osti kumpaakin tuotetta?

Ratkaistavana on Diofantoksen yhtälö 15x + 11y = 137. Ratkaistaan se siirtymällä kongruenssiin

Koska syt(15, 11) = 1, niin Diofantoksen yhtälö -sivun lauseen mukaan kongruenssilla on ratkaisu x, jolle pätee 0 < x < 10. Yksi tapa ratkaista kongruenssi on kokeilla kaikki luvut 0,..., 10. Tämä on helppo ratkaisu varsinkin pienillä luvuilla.

Toisen tavan tarjoaa edellämainitun lauseen todistus. Koska syt(15, 11) = 1, niin on olemassa sellaiset luvut u ja v, joilla 15u + 11v = 1. Esimerkiksi Eukleideen algoritmia käyttäen löydetään luvut u = 3 ja v = 4, jotka toteuttavat yhtälön. Kongruenssin eräs ratkaisu on siis x = 137u = 411. Koska kongruenssin kaikki ratkaisut ovat keskenään kongruentteja modulo 11, niin pienin positiivinen ratkaisu on nyt x = 4.

Alkuperäisen tehtävän ratkaisuksi saadaan siis x = 4 ja y = 7. Huomaa, että pienin positiivinen ratkaisu ei välttämättä ole alkuperäisen tehtävän ratkaisu, tässä esimerkissä näin kuitenkin on.

Linkit:
Diofantoksen yhtälö
Eukleideen algoritmi
Konruenssi