Lineární kongruence

Řešením lineární kongruence rozumíme nalezení všech celých čísel splňujících
kde a

Buďte a .
Kongruence má řešení právě tehdy, když .

ji řeší právě tehdy, když existuje takové, že řeší lineární diofantickou rovnici .
Všechna řešení lineární kongruence v jsou pak