Równoważne stwierdzenia

Przypomnijmy sobie najpierw następujące równoważne stwierdzenia
  • AB (mod C) A \equiv B\ (\text{mod }C)
  • A mod C=B mod C A \text{ mod } C = B \text{ mod }C
  • C  (AB) C \ |\ (A - B) (symbol | oznacza "dzieli" albo "jest dzielnikiem" )
  • A=B+KC A = B + K \cdot C (gdzie K K jest pewną liczbą całkowitą)
Możemy więc swobodnie przechodzić pomiędzy równoważnymi sposobami na wyrażenie tego samego faktu.
Dla przykładu następujące są równoważne:
  • 1323 (mod 5) 13 \equiv 23\ (\text{mod }5)
  • 13 mod 5=23 mod 5 13 \text{ mod } 5 = 23 \text{ mod }5
  • 5  (1323) 5 \ |\ (13 - 23) , (5  10 (5 \ |\ -10 , co jest prawdą, ponieważ 5(2)=10) \bf{5 \cdot (-2) = -10} )
  • 13=23+K5 13 = 23 + K \cdot 5 . Możemy spełnić to równanie dla K=2 \bf{K = -2} : 13=23+(2)5 13 = 23 + (-2) \cdot 5

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

ciasto

Przekonaj się, że kawałki użyte w poprzednim przykładzie mają następujące własnoś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 z kawałkami spełniającymi powyższe własności nazywa się relacją równoważności .
Relacja równoważności określa jak kroimy nasze ciastko (albo jak dzielimy zbiór interesujących nas liczb na ( klasy równoważności ).
Relacje równoważności muszą mieć następujące własności:
  • 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
W szczególności, w poprzednim przykładzie
  • 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ą mod C=B \text{mod } C = B
  • Sposób pocięcia ciasta na kawałki: używając relacji przystawania modulo C, (mod C) \equiv (\text{mod } C)
Z tego powodu mówimy, że Przystawanie modulo C jest relacją równoważności . Dzieli ona zbiór liczb całkowitych na C różnych klas równoważności.

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

Wiedząc, że przystawanie modulo jest relacją równoważności, możemy wnioskować o pewnych własnościach, jakie musi ono posiadać.
Relacje równoważności to relacje, które mają następujące własności:
  • zwrotne: A jest w relacji z A
  • Jest symetryczne: jeśli A jest w relacji z B to B jest w relacji z A
  • przechodnie: jeśli A jest w relacji z B i B jest w relacji z C, to A jest w relacji z C
Ponieważ przystawanie modulo jest relacja równoważności, oznacza to, że:
  • AA (mod C) A \equiv A \ (\text{mod } C)
  • Jeśli AB (mod C) A \equiv B \ (\text{mod }C) , to BA (mod C) B \equiv A \ (\text{mod }C)
  • Jeśli AB (mod C) A \equiv \bf{B} \ (\text{mod } C) i BD (mod C) \bf{B} \equiv D \ (\text{mod } C) to AD (mod C) \bf{A \equiv D} \ (\text{mod } C)

Przykład

mod5
Zastosujmy te własności na konkretnym przykładzie, na przykład mod 5: \text{mod }5:
  • 33 (mod 5) 3 \equiv 3\ (\text{mod } 5) (zwrotność)
  • if 38 (mod 5) 3 \equiv 8\ (\text{mod } 5) then 83 (mod 5) 8 \equiv 3\ (\text{mod }5) (symetryczność)
  • if 38 (mod 5) 3 \equiv 8\ (\text{mod }5) and if 818 (mod 5) 8 \equiv 18\ (\text{mod }5) then 318 (mod 5) 3 \equiv 18\ (\text{mod }5) (przechodniość)
Ładowanie