Diofantická rovnice

Diofantická rovnice je polynomiální rovnice, ve které jsou proměnné pouze celočíselní.

Definice

Lineární diofantická rovnice je libovolná rovnice typu $a·x + b·y = c$ s neznámými $x,y$ pro které platí $x, y, a, b, c ∈ ℤ$.

Věta o existenci řešení

Lineární diofantická rovnice $a·x + b·y = c$ má alespoň jedno řešení právě tehdy, když $gcd(a, b)|c$.

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ť $a ,b$ jsou nenulové celá čísla a dvojice $(x, y)$ je řešením rovnice $a·x + b·y = c$. Potom množina všech celočíselných řešení této rovnice je $\{( x_0 + (b/gcd(a,b))·k, y_0 - (a/gcd(a,b))·k): k ∈ ℤ\}$

Důkaz

Jsou-li (x, y) i (x₀, y₀) řešeními, bude platit a·x + b·y = a·x₀ + b·y₀, tedy a·x - a·x₀ = b·y - b·y₀.

Vydělením obou stran číslem d = gcd(a, b) dostaneme a/d·(x−x₀) = b/d·(y₀−y).

Víme ale, že gcd(a/d,b/d) = 1, takže musí platit ad|(y₀−y) a bd|(x−x₀) neboli (x−x₀) = u(b/d) a (y₀−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í.