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 będzie liczbą naturalną. Mówimy, że liczba całkowita
przystaje do liczby całkowitej
modulo
, jeśli
(tzn.
dzieli różnicę liczb
i
). Tak określoną relację nazywamy kongruencją (przystawaniem modulo
) i piszemy
.
Uwaga:
Zapis oznacza podzielność liczby
przez liczbę
, np.
odczytamy jako "
dzieli
" lub
jest podzielne przez
.
Przykład:
Możemy napisać , ponieważ reszta z dzielenia obu tych liczb przez
jest taka sama. Lub patrząc na to inaczej:
jest liczbą podzielną przez
.
Podobnie , bo
oraz
.
Nie prawda, że , ponieważ
, a
nie jest podzielne przez
.
Własności
Kongruencje mają następujące własności:
1) (zwrotność kongruencji).
2) Jeśli to
(symetryczność kongruencji).
3) Jeśli i
to
(przechodniość kongruencji).
4) Niech ,
,
i
będą liczbami całkowitymi oraz
będzie liczbą naturalną. Wówczas jeśli
i
to:
- ,
- ,
- .
5) Jeśli to
, gdzie
jest dowolną liczbą całkowitą.
Przykład:
Sprawdźmy, że własności podane w punkcie 4) zachodzą dla ,
,
,
przy
. Będzie to jednocześnie przykład zastosowania podanych w tym punkcie własności.
Mamy oraz
.
Dodajmy te kongruencje stronami.
, jest to liczba podzielna przez
, zatem własność dodawania kongruencji stronami zachodzi.
Podobnie z odejmowaniem:
,
.
W przypadku mnożenia stronami:
, jest to liczba parzysta, zatem własność jest spełniona.