Kongruencja (przystawanie) jest pojęciem z teorii liczb związanym z resztą z dzielenia. Jeśli dwie liczby mają jednakową resztę z dzielenia przez daną trzecią liczbę mówimy, że pozostają ze sobą w kongruencji (przystają do siebie).
Pojęcie kongruencji jako pierwszy wprowadził Gauss w swoim dziele Disquisitiones Arithmeticae wydanym w 1801 roku. Nazwa pochodzi od łacińskiego słowa congruere - iść razem, zgadzać się.
Definicja
Niech \(m\) będzie liczbą naturalną. Mówimy, że liczba całkowita \(a\) przystaje do liczby całkowitej \(b\) modulo \(m\), jeśli \(m|a-b\) (tzn. \(m\) dzieli różnicę liczb \(a\) i \(b\)). Tak określoną relację nazywamy kongruencją (przystawaniem modulo \(m\)) i piszemy \(a\equiv b \pmod{m} \).
Uwaga:
Zapis \(m|n\) oznacza podzielność liczby \(n\) przez liczbę \(m\), np. \(10|50\) odczytamy jako "\(10\) dzieli \(50\)" lub \(50\) jest podzielne przez \(10\).
Przykład:
Możemy napisać \(5\equiv 11 \pmod{2} \), ponieważ reszta z dzielenia obu tych liczb przez \(2\) jest taka sama. Lub patrząc na to inaczej: \(5-11=-6\) jest liczbą podzielną przez \(2\).
Podobnie \(105\equiv 101 \pmod{2} \), bo \(105-101=4\) oraz \(2|4\).
Nie prawda, że \(102\equiv 100 \pmod{3} \), ponieważ \(102-100=2\), a \(2\) nie jest podzielne przez \(3\).
Własności
Kongruencje mają następujące własności:
1) \(a\equiv a \pmod{m} \) (zwrotność kongruencji).
2) Jeśli \(a\equiv b \pmod{m} \) to \(b\equiv a \pmod{m} \) (symetryczność kongruencji).
3) Jeśli \(a\equiv b \pmod{m} \) i \(b\equiv c \pmod{m} \) to \(a\equiv c \pmod{m} \) (przechodniość kongruencji).
4) Niech \(a\), \(b\), \(c\) i \(d\) będą liczbami całkowitymi oraz \(m\) będzie liczbą naturalną. Wówczas jeśli \(a\equiv b \pmod{m} \) i \(c\equiv d \pmod{m} \) to:
- \(a+c\equiv b+d \pmod{m} \),
- \(a-c\equiv b-d \pmod{m} \),
- \(ac\equiv bd \pmod{m} \).
5) Jeśli \(a\equiv b \pmod{m} \) to \(a^k \equiv b^k \pmod{m} \), gdzie \(k\) jest dowolną liczbą całkowitą.
Przykład:
Sprawdźmy, że własności podane w punkcie 4) zachodzą dla \(a = 5\), \(b=11\), \(c=105\), \(d=101\) przy \( \pmod{2} \). Będzie to jednocześnie przykład zastosowania podanych w tym punkcie własności.
Mamy \(5\equiv 11 \pmod{2} \) oraz \(105\equiv 101 \pmod{2} \).
Dodajmy te kongruencje stronami.
\(5+105\equiv 11+101 \pmod{2} \)
\(110\equiv 122 \pmod{2} \)
\(122-110=12\), jest to liczba podzielna przez \(2\), zatem własność dodawania kongruencji stronami zachodzi.
Podobnie z odejmowaniem:
\(5-105\equiv 11-101 \pmod{2} \)
\(-100\equiv -90 \pmod{2} \)
\(-100-(-90)=-100+90=-10\), \(2|-10\).
W przypadku mnożenia stronami:
\(5 \cdot 105\equiv 11 \cdot 101 \pmod{2} \)
\(525\equiv 1111 \pmod{2} \)
\(525-1111=586\), jest to liczba parzysta, zatem własność jest spełniona.