Kongruencja to relacja okre¶lona w zbiorze liczb całkowitych.
Kongruencja modulo n nazywana jest też przystawaniem liczb "modulo n".
Liczby całkowite a i b przystaj± modulo n (pozostaj± w kongruencji modulo n), co zapisuje się: a ≡ b (mod n), jeżeli ich różnicaa-bdzieli się bez reszty przez n. Równoważnie: je¶li liczby a i b daj± w dzieleniu przez n tę sam± resztę.
Przykład:
Liczby 5 i 11 przystaj± modulo 3:
:11 ≡ 5 (mod 3)
ponieważ ich różnica, czyli 6, dzieli się bez reszty przez 3. Równoważnie, w dzieleniu z reszt± obu liczb przez 3 otrzymujemy tę sam± resztę 2:
Własno¶ci kongruencji:
zwrotno¶ć:
::dla każdej liczby całkowitej a: a ≡ a (mod n).
symetria:
::jeżeli dla liczb całkowitych a i b: a ≡ b (mod n), to: b ≡ a (mod n).
przechodnio¶ć:
:: jeżeli dla liczb całkowitych a, b i c: a ≡ b (mod n) i b ≡ c (mod n), to: a ≡ c (mod n).
Kongruencja jest zatem relacj± równoważno¶ci
Własno¶ci kongruencji:
kongruencja sumy
::Jeżeli a ≡ p (mod n) i b ≡ q (mod n), to (a+b) ≡ (p+q) (mod n)
kongruencja iloczynu
::Jeżeli a ≡ p (mod n) i b ≡ q (mod n), to a·b ≡ p·q (mod n)
Powyższe dwie własno¶ci s± podstaw± m.in. obliczeń kontrolnych w rachunkach pisemnych, np. "reguły dziewi±tek".
Kongruencje można też okre¶lać w dowolnych pier¶cieniach.