Diofantoksen yhtälö

Diofantoksen yhtälö on yhtälö, jolle etsitään kokonaislukuratkaisua. Lineaarisen kahden tuntemattoman Diofantoksen yhtälön ax + my = c (luvut a,m ja c ovat tunnettuja) ratkaiseminen on ekvivalenttia kongruenssin

ratkaisemisen kanssa. Seuraavaksi todistetaan tätä kongruenssia koskeva tulos.

Lause. Jos syt(a,m) = 1, kongruensilla ax c (mod m) on yksikäsitteinen ratkaisu x välillä 0 < x < m - 1.

Todistus. Oletuksen syt(a,m) = 1 nojalla on olemassa sellaiset luvut u ja v, että au + mv = 1. Täten a(uc) + m(vc) = c ja kongruenssin ax c (mod m) yksi ratkaisu on x = uc. Lisäksi kongruenssin kaikki ratkaisut ovat keskenään kongruentteja. Nimittäin, jos x₁ ja x₂ ovat kongruenssin kaksi eri ratkaisua, niin ax₁ ax₂ (mod m). Sivulla Kongruenssi olevan lauseen kohdan (ii) mukaan tästä seuraa, että x₁ x₂ (mod m). Ratkaisuista on siis tarkalleen yksi halutulla välillä.

Linkit:
Suurin yhteinen tekijä
Kongruenssi
Esimerkki Diofantoksen yhtälön ja kongruenssin käytöstä