@andreaLineární kongruence: pro daná celá čísla a, b a m > 1 hledáme celá číslo x takové, že platí a·x ≡ b mod m.
Věta
Lineární kongruence má řešení právě tehdy, když gcd(a, m)|b. Všechna řešení jsou tvaru x = x0 + k·m/gcd(a, m), k ∈ ℤ a pro x0 existuje y0 takové, že dvojice (x0, y0) je řešením rovnice a·x+m·y=b.
Důkaz:
Víme že, ax≡b(mod m) znamená totéž, jako že ax−b je dělitelné m, tedy že pro nějaké celé číslo j platí ax−b=jm. To bude ovšem platit právě tehdy, když rovnice a.x+m.y=b má nějaké řešení. K tomu je nutné a stačí, aby gcd(a, m)|b.
Rovnice a·x+m·y=b má podle věty o konstrukci všech řešení, právě když gcd(a, m)|b. Podle Věty4 jsou všechna řešení tvaru (x0 + m/gcd(a, m)·k, y0−a/gcd(a, m)·k),kde k ∈ Z, nás ovšem zajímá pouze složka x, takže všechna řešení linární kongruence ax≡b(modm) mají tvar x= x0+k·m/gcd(a, m)
Věta o existenci a počtu řešení lineární kongruence:
Jestliže gcd(a, m)|b, potom kongruencea x≡b(mod m) má konečně mnoho řešení modulo m. Těchto řešení je přesně gcd(a, m) a jsou dána výrazem
gcd(a, m), kde x0 je z dvojice (x0, y0), kterě je nějakým řešením rovnice a·x+m·y=b.
Důkaz:
Plyne ze znalosti množiny řešení lineárních diofantických rovnic a vlastnosti kongruence modulo m.