Kongruencja

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.

Polecamy również:

Cechy podzielności liczb

Z podzielnością liczb wiążą się następujące zasady: Liczba jest podzielna przez 2 jeśli jej ostatnia cyfra jest... Więcej »
Liczby pierwsze i liczby złożone

W teorii liczb niezmiernie ważne jest zagadnienie liczb pierwszych i złożonych. Są to pojęcia zarazem bardzo elementarne - jest je w stanie zrozumieć nawet amator nie zajmujący się matematyką na codzień - jak i wysoce zaawansowane - znajdowanie liczb pierwszych jest jednym z najważniejszych obecnie problemów... Więcej »
Największy wspólny dzielnik

W zagadnieniach związanych z podzielnością liczb wygodnie jest posługiwać się pojęciem największego wspólnego dzielnika (NWD). Największym wspólnym dzielnikiem dwóch liczb nazywamy największą liczbę naturalną dzielącą obie te liczby. Więcej »
Najmniejsza wspólna wielokrotność

Zagadnieniem bliźniaczym do największego wspólnego dzielnika jest znajdowanie najmniejszej wspólnej wielokrotności (NWW). Najmniejszą wspólną wielokrotnością dwóch liczb nazywamy najmniejszą liczbę naturalną, której dzielnikami są te liczby. Pojęcie to można uogólnić dla... Więcej »
Reszta z dzielenia

W zagadnieniach związanych z podzielnością istotne miejsce zajmuje reszta z dzielenia. Dzielenie liczb całkowitych może przebiegać na dwa sposoby, z resztą oraz bez reszty. Więcej »

Komentarze (0)

Kongruencja

Definicja

Uwaga:

Przykład:

Własności

Przykład:

Polecamy również:

Zobacz również

Cechy podzielności liczb

Liczby pierwsze i liczby złożone

Największy wspólny dzielnik

Najmniejsza wspólna wielokrotność

Reszta z dzielenia

Losowe zadania

Wypór wody i benzyny

Średnia arytmetyczna

Oblicz wartościowość galu w jego soli

Teoria heliocentryczna i geocentryczna

Asymilacja azotu atmosferycznego