Diofantická rovnice je polynomiální rovnice, ve které jsou proměnné pouze celočíselní.
Definice
Lineární diofantická rovnice je libovolná rovnice typu s neznámými pro které platí .
Věta o existenci řešení
Lineární diofantická rovnice má alespoň jedno řešení právě tehdy, když .
Důkaz
⇒: Nechť existují x, y ∈ ℤ taková, že a·x + b·y = c. Protože gcd(a, b) dělí a i b, tak dělí i a·x + b·y, což je c.
⇐: Nechť platí c=k.gcd(a, b). Víme, že lze psát gcd(a, b) = Aa+Bb pro jistá A, B ∈ ℤ, tak že bude c=k.gcd(a, b) = kAa+kBb, tedy celá čísla x=kA, y=kB řeší rovnici a·x + b·y = c.
Věta o konstrukci všech řešení
Nechť jsou nenulové celá čísla a dvojice je řešením rovnice . Potom množina všech celočíselných řešení této rovnice je
Důkaz
Jsou-li (x, y) i (x0, y0) řešeními, bude platit a·x + b·y = a·x0 + b·y0, tedy a·x - a·x0 = b·y - b·y0.
Vydělením obou stran číslem d = gcd(a, b) dostaneme a/d·(x−x0) = b/d·(y0−y).
Víme ale, že gcd(a/d,b/d) = 1, takže musí platit ad|(y0−y) a bd|(x−x0) neboli (x−x0) = u(b/d) a (y0−y) = v(a/d) pro nějaká celočíselná u, v. Je tedy a/d·u·b/d=a/d·v·b/d, neboli u=v po vykrácení.