Kongruencje
Jeśli $a$, $b$ i $m$ są liczbami całkowitymi oraz zachodzi $m|a-b$, to mówimy, że liczba $a$ przystaje do liczby $b$ modulo $m$ i zapisujemy $a \equiv b \pmod m$. Relację tę nazywamy kongruencją.
Dwie liczby przystają do siebie według modułu $m$, jeśli mają przy dzieleniu przez ten moduł takie same reszty.
Przykłady:
$23 \equiv 11 \pmod 6$, bo $6|23-11$
$7 \equiv 3 \pmod 2$, bo $2|7-3$
$16 \equiv -6 \pmod{11}$, bo $11|16-(-6)$
$-5 \equiv 5 \pmod{10}$, bo $10|-5-5$
$-16 \equiv -1 \pmod 3$, bo $3|-16-(-1)$
$18 \equiv 0 \pmod 9$, bo $9|18-0$
Kongruencje mają wiele własności przypominających własności równości:
- zwrotność - dla dowolnej liczby całkowitej $a$ zachodzi $a \equiv a \pmod m$.
- symetryczność - kongruencja $a \equiv b \pmod m$ pociąga za sobą kongruencję $b \equiv a \pmod m$.
- przechodniość - z kongruencji $a \equiv b \pmod m$ i $b \equiv c \pmod m$ wynika zawsze kongruencja $a \equiv c \pmod m$.
Kongruencje o tym samym module można dodawać, odejmować lub mnożyć stronami, tzn. z kongruencji
$a \equiv b \pmod m$ i $c \equiv d \pmod m$ wynikają kongruencje $a \pm c \equiv b \pm d \pmod m$ oraz $ac \equiv bd \pmod m$.
Nie można natomiast dzielić stronami kongruencji. Na przykład z kongruencji $6 \equiv 2 \pmod 4$ oraz $2 \equiv 2 \pmod 4$
nie wynika kongruencja $3 \equiv 1 \pmod 4$. Jeśli natomiast $d$ jest dzielnikiem liczb $a,b$ i $m$, to z kongruencji $a \equiv b \pmod m$, wynika kongruencja $\frac{a}{d} \equiv \frac{b}{d} \pmod{ \frac{m}{d} }$.
Można także przenosić wyrazy z jednej strony kongruencji na drugą, zmieniając ich znaki. Obie strony kongruencji można podnosić
do tej samej potęgi o wykładniku naturalnym, tzn. z kongruencji $a \equiv a \pmod m$ wynika kongruencja $a^n \equiv a^n \pmod m$.
W kongruencji mamy prawo zastąpić dany składnik lub czynnik przez inny przystający modulo $m$. Ostatnia własność jest często wykorzystywana do dowodzenia twierdzeń lub bardzo pomocna przy rozwiązywaniu zadań.