Relații de echivalență

Expresii echivalente

• $A\equiv B(\text{mod }C)$‍
• $A\text{ mod }C=B\text{ mod }C$‍
• $C|(A-B)$‍ (Simbolul | înseamnă "divide pe" sau "este un divizor al lui")
• $A=B+K\cdot C$‍ (unde $K$‍ este un număr întreg)

• $13\equiv 23(\text{mod }5)$‍
• $13\text{ mod }5=23\text{ mod }5$‍
• $5|(13-23)$‍, $(5|-10$‍, lucru care este adevărat din moment ce $\mathbf{5}\times \mathbf{(}\mathbf{-}\mathbf{2}\mathbf{)}\mathbf{=}\mathbf{-}\mathbf{10}\mathbf{)}$‍
• $13=23+K\cdot 5$‍. Condiția aceasta este îndeplinită de $\mathbf{K}\mathbf{=}\mathbf{-}\mathbf{2}$‍: $13=23+(-2)\times 5$‍

Congruența modulo n este o relație de echivalență

• Fiecare pereche dintr-un sector este formată din valori asociate una alteia
• Nu vom găsi niciodată o valoare în mai mult de un sector (spunem că sectoarele sunt mutual disjuncte)
• Dacă am pune laolaltă toate sectoarele, ele ar forma un cerc care conține toate valorile

• Cercul: O colecție a tuturor valorilor care ne interesează
• Un sector de cerc: O clasă de echivalență
• Modul în care tăiem cercul în sectoare: relație de echivalență

• Cercul: Colecția tuturor numerelor întregi
• Un sector de cerc etichetat $B$‍: Clasa de echivalență care conține toate valorile $\text{mod }C=B$‍
• Modul în care tăiem cercul în sectoare: Folosind relația de congruență modulo C, $\equiv (\text{mod }C)$‍

De ce ne interesează faptul că relația de congruență modulo C este o relație de echivalență?

• Sunt reflexive: A este în relație cu A
• Sunt simetrice: dacă A este în relație cu B, atunci B este în relație cu A
• Sunt tranzitive: Dacă A este în relație cu B și B este în relație cu C atunci A este în relație cu C

• $A\equiv A(\text{mod }C)$‍
• dacă $A\equiv B(\text{mod }C)$‍ atunci $B\equiv A(\text{mod }C)$‍
• dacă $A\equiv \mathbf{B}\mathbf{(}\text{mod }\mathbf{C}\mathbf{)}$‍ și $\mathbf{B}\equiv \mathbf{D}\mathbf{(}\text{mod }\mathbf{C}\mathbf{)}$‍ atunci $\mathbf{A}\equiv \mathbf{D}\mathbf{(}\text{mod }\mathbf{C}\mathbf{)}$‍

Exemplu

• $3\equiv 3(\text{mod }5)$‍ (proprietatea de reflexivitate)
• dacă $3\equiv 8(\text{mod }5)$‍ atunci $8\equiv 3(\text{mod }5)$‍ (proprietatea de simetrie)
• dacă $3\equiv 8(\text{mod }5)$‍ și dacă $8\equiv 18(\text{mod }5)$‍ atunci $3\equiv 18(\text{mod }5)$‍ (proprietatea de tranzitivitate)