Conţinutul principal

Congruența modulo

Congruența Modulo

Putem vedea o expresie precum:

$A \equiv B (mod C)$ ‍

Aceasta înseamnă că

A

este congruent cu

B

modulo

C

Vom discuta sensul congruenței modulo prin efectuarea unui experiment de gândire cu operatorul obișnuit de modulo.

Să ne imaginăm calculul lui mod 5 pentru toate numerele întregi:

Să presupunem că am etichetat 5 sectoare 0, 1, 2, 3, 4. Apoi, am pus fiecare număr întreg în acel sector care corespunde valorii întregului mod 5.
Gândește-te la aceste sectoare ca la niște găleți care conțin, fiecare, câte un set de numere. De exemplu, 26 ar intra în sectorul cu eticheta 1, pentru că

26 mod 5 = 1

.
Mai sus este o figură cu niște numere întregi pe care le-am găsi în fiecare sector.

Ar fi util să existe un mod în care să exprimăm faptul că numerele sunt în acelaşi sector. (Observăm că 26 se află în același sector cu 1, 6, 11, 16, 21 în exemplul de mai sus).

Exprimăm apartenența numerelor la același sector spunând că ele fac parte din aceeași clasă de echivalență.
Notația în limbaj matematic este:

A \equiv B (mod C)

Expresia de mai sus se pronunță astfel:

A

este congruent cu

B

modulo

C

Examinând expresia mai în detaliu:

$\equiv$ ‍ este simbolul pentru congruență, ceea ce înseamnă că valorile $A$ ‍ și $B$ ‍ sunt în aceeași clasă de echivalență.
$(mod C)$ ‍ ne spune ce operație am aplicat asupra lui $A$ ‍ și $B$ ‍.
când le avem pe ambele, numim expresia “ $\equiv$ ‍” congruență modulo $C$ ‍.

ex.

26 \equiv 11 (mod 5)

26 mod 5 = 1

deci este în clasa de echivalență a lui 1,

11 mod 5 = 1

deci este tot în clasa de echivalență a lui 1.

Observație: aceasta diferă de

A mod C

26 \neq 11 mod 5

Aprofundarea Congruenței Modulo

Putem înțelege mai bine ce înseamnă congruența modulo $C$ ‍.
Mai întâi, vom eticheta $C$ ‍ sectoare $0, 1, 2, \dots, C - 2, C - 1$ ‍.
Apoi, punem fiecare dintre numerele întregi în sectorul care corespunde valorii întregului $mod C$ ‍.
Mai jos este o figură care arată câteva valori reprezentative pe care le-am găsi în fiecare dintre sectoare.

Dacă ne-am uita la găleata etichetată cu 0 am găsi:

$\dots, - 3 C, - 2 C, - C, 0, C, 2 C, 3 C, \dots$ ‍

Dacă ne-am uita la găleata etichetată cu 1 am găsi:

$\dots, 1 - 3 C, 1 - 2 C, 1 - C, 1, 1 + C, 1 + 2 C, 1 + 3 C, \dots$ ‍

Dacă ne-am uita la găleata etichetată cu 2 am găsi:

$\dots, 2 - 3 C, 2 - 2 C, 2 - C, 2, 2 + C, 2 + 2 C, 2 + 3 C, \dots$ ‍

Dacă ne-am uita la găleata etichetată cu C - 1 am găsi:

$\dots, - 2 C - 1, - C - 1, - 1, C - 1, 2 C - 1, 3 C - 1, 4 C - 1 \dots$ ‍

Din acest experiment putem face o observație cheie:
Valorile din fiecare sector sunt egale cu eticheta sectorului plus sau minus câțiva multiplii de $C$ ‍.
Asta înseamnă că diferența dintre oricare două valori dintr-un sector este un multiplu de $C$ ‍.
Această observaţie ne poate ajuta să înţelegem expresiile echivalente şi clasele de echivalenţă următoare.

Vrei să te alături conversației?

Conectare

Ordonare după:

Nici o postare încă.

Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.

Teoria informației și criptografie

Curs: Teoria informației și criptografie > Unitatea 2