Relacje równoważności

Równoważne stwierdzenia

• $A \equiv B\ (\text{mod }C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• $A \text{ mod } C = B \text{ mod }C$A, start text, space, m, o, d, space, end text, C, equals, B, start text, space, m, o, d, space, end text, C
• $C \ |\ (A - B)$C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (symbol | oznacza "dzieli" albo "jest dzielnikiem" )
• $A = B + K \cdot C$A, equals, B, plus, K, dot, C (gdzie $K$K jest pewną liczbą całkowitą)

• $13 \equiv 23\ (\text{mod }5)$13, \equiv, 23, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis
• $13 \text{ mod } 5 = 23 \text{ mod }5$13, start text, space, m, o, d, space, end text, 5, equals, 23, start text, space, m, o, d, space, end text, 5
• $5 \ |\ (13 - 23)$5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis ( $5 \ |\ -10$5, space, vertical bar, space, minus, 10, co jest prawdą, ponieważ ${5 \cdot (-2) = -10}$5, dot, left parenthesis, minus, 2, right parenthesis, equals, minus, 10 )
• $13 = 23 + K \cdot 5$13, equals, 23, plus, K, dot, 5. Możemy spełnić to równanie dla $\bf{K = -2}$K, equals, minus, 2: $13 = 23 + (-2) \cdot 5$13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, dot, 5

Przystawanie modulo jest relacją równoważności

• Każda para liczb w danym kawałku pozostaje ze sobą w relacji
• Nigdy nie znajdziemy danej liczby w więcej niż jednym kawałku (zbiory liczb znajdujące się w różnych kawałkach są ze sobą rozłączne)
• Jeśli połączymy zbiory znajdujące się we wszystkich kawałkach dostaniemy "ciasto" zawierające wszystkie liczby

• Ciasto: zbiór wszystkich liczb, które nas interesują
• Kawałek ciasta: klasa równoważności
• Sposób pocięcia ciasta na kawałki: określa relację równoważności

• Ciasto: zbiór iczb całkowitych
• Kawałek ciasta oznaczony $B$B: Klasa równoważności, w której wszystkie wartości spełniają $\text{mod } C = B$start text, m, o, d, space, end text, C, equals, B
• Sposób pocięcia ciasta na kawałki: używając relacji przystawania modulo C, $\equiv (\text{mod } C)$\equiv, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Czemu dbamy o to, że przystawanie modulo jest relacją równoważności?

• Są zwrotne: A jest w relacji z A
• Jest symetryczne: jeśli A jest w relacji z B to B jest w relacji z A
• Są przechodnie: jeśli A jest w relacji z B i B jest w relacji z C, to A jest w relacji z C

• $A \equiv A \ (\text{mod } C)$A, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• Jeśli $A \equiv B \ (\text{mod }C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, to $B \equiv A \ (\text{mod }C)$B, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• Jeśli $A \equiv \bf{B} \ (\text{mod } C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis i $\bf{B} \equiv D \ (\text{mod } C)$B, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis to $\bf{A \equiv D} \ (\text{mod } C)$A, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Przykład

• $3 \equiv 3\ (\text{mod } 5)$3, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (zwrotność)
• if $3 \equiv 8\ (\text{mod } 5)$3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis then $8 \equiv 3\ (\text{mod }5)$8, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (symetryczność)
• if $3 \equiv 8\ (\text{mod }5)$3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis and if $8 \equiv 18\ (\text{mod }5)$8, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis then $3 \equiv 18\ (\text{mod }5)$3, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (przechodniość)