1. Strona główna
    2. /
  2. Matematyka
    3. /
  3. Kongruencja

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 »

Zobacz również

Losowe zadania

Komentarze (0)
Wynik działania 3 + 5 =
Ostatnio komentowane
Tyrteusz
Kutas
• 2023-12-11 09:27:47
Piramida płci i wieku w Polsce
a
• 2023-12-10 16:34:11
Opracowanie
sdf
• 2023-12-09 16:26:23
Filomaci i Filareci
eseba karai
• 2023-12-09 13:28:33
Semiotyka
OOOO Pan Pan Paweł!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
• 2023-12-07 14:50:52