Rechenregeln für Kongruenzen

Elementare Rechenregeln

Für das Rechnen mit Kongruenzen lassen sich einige elementare Rechenregeln aufstellen.

Satz 164R (Eigenschaften von Kongruenzen)

Gilt ab(modm)a \equiv b \pmod m und cd(modm)c \equiv d \pmod m und bx(modm)b \equiv x \pmod m, so gilt:
  1. aamodma \equiv a \mod{m} (Reflexivität)
  2. Aus abmodma \equiv b \mod{m} folgt bamodmb \equiv a \mod{m} (Symmetrie)
  3. Aus abmodma \equiv b \mod{m} und bcmodmb \equiv c \mod{m} folgt acmodma \equiv c \mod{m} (Transitivität)
  4. nanbmodmna \equiv nb \mod{m}
  5. a+cb+dmodma + c \equiv b + d \mod{m} acbdmodma - c \equiv b - d \mod{m}
  6. acbdmodmac \equiv bd \mod{m} anbnmodma^n \equiv b^n \mod{m}

Beweis

abmodma \equiv b \mod m bedeutet mbam|b-a, damit sind (i) und (ii) trivial.
(iii) abmodma \equiv b \mod{m} bedeutet mbam|b-a und bcmodmb \equiv c \mod{m} bedeutet mcbm|c-b und damit ist auch m(ba+cb)    m(ca)m|(b-a+c-b)\implies m|(c-a), also acmodma \equiv c \mod{m}
(iv) Wegen mn(ba)m|n(b-a) und mnbnam|nb-na
(v) abmodma \equiv b \mod{m} bedeutet mbam|b-a und cd(modm)c \equiv d \pmod m bedeutet mdcm|d-c, also mdc+bam|d-c+b-a     m(b+d)(a+c)\implies m|(b+d)-(a+c) Subtraktion analog.
(vi) Aus mbam|b-a und mdcm|d-c folgt m(ba)dm|(b-a)d also mbdadm|bd-ad und m(dc)am|(d-c)a also madacm|ad-ac. Mit (v) erhalten wir mbdacm|bd-ac
anbnmodma^n \equiv b^n \mod{m} zeigt man unter Benutzung des eben Bewiesenen mittels vollständiger Induktion. \qed

Abgeleitete Rechenregeln

  1. Für t0t \ne 0 gilt: tatbmodtm\qquad t \cdot a \equiv t \cdot b \mod |t| \cdot m
  2. Ist kk ein Teiler von mm, dann gilt: abmodk\qquad a \equiv b \mod k
  3. Sei cacbmodnc \cdot a \equiv c \cdot b \mod n sowie d=ggT(c,n)d = \ggT(c,n) (größter gemeinsamer Teiler), dann gilt: abmod(n/d)a \equiv b \mod(n/d)Sind cc und nn teilerfremd, also d=1d = 1, dann folgt sofort abmodna \equiv b \mod n
  4. Sei cacbmodpc \cdot a \equiv c \cdot b \mod p mit einer Primzahl pp, wobei pp kein Teiler von cc ist. Dann gilt: abmodpa \equiv b \mod p
  5. Sei abmodna \equiv b \mod n und c>0c > 0. Dann gilt: cacbmod(cn)c \cdot a \equiv c \cdot b \mod(c \cdot n)
  6. Sei abmodna \equiv b \mod n. Ferner sei d>0d > 0 ein Teiler der ganzen Zahlen aa, bb. Dann gilt: (a/d)(b/d)mod(n/d)(a/d) \equiv (b/d) \mod(n/d)
  7. Für jede ungerade Zahl aa gilt a21mod8a^2 \equiv 1 \mod 8Mit anderen Worten: Teilt man a2a^2 durch 8, dann bleibt als Rest 1.
  8. Für jede ganze Zahl gilt entweder a30mod9a^3 \equiv 0 \mod 9 oder a31mod9a^3 \equiv 1 \mod 9 oder a38mod9a^3 \equiv 8 \mod 9Mit anderen Worten: Entweder a3a^3 ist durch 9 teilbar oder es bleibt als Rest 1 oder 8.
  9. Für jede ganze Zahl gilt entweder a30mod7a^3 \equiv 0 \mod 7 oder a31mod7a^3 \equiv 1 \mod 7 oder a36mod7a^3 \equiv 6 \mod 7Mit anderen Worten: Entweder a3a^3 ist durch 7 teilbar oder es bleibt als Rest 1 oder 6.
  10. Für jede ganze Zahl gilt entweder a40mod5a^4 \equiv 0 \mod 5 oder a41mod5a^4 \equiv 1 \mod 5Mit anderen Worten: Entweder a4a^4 ist durch 5 teilbar oder es bleibt als Rest 1
  11. Ist aa sowohl eine Quadratzahl als auch eine Kubikzahl (z.B. a=64a = 64) dann gilt entweder a0mod36a \equiv 0 \mod 36 oder a1mod36a \equiv 1 \mod 36 oder a9mod36a \equiv 9 \mod 36 oder a28mod36a \equiv 28 \mod 36
  12. Sei pp eine Primzahl mit n<p<2nn < p < 2n. Dann gilt(2nn)0modp{\chooseNT {2n} n} \equiv 0 \mod{p}
  13. Sei aa eine ungerade ganze Zahl. Ferner sei n>0n > 0. Dann gilt: a2n1mod2n+2a^{2^n} \equiv 1 \mod 2^{n+2}
  14. Seien abcdmodna \cdot b \equiv c \cdot d \mod n, bdmodnb \equiv d \mod n sowie ggT(b,n)=1\ggT(b,n) = 1 (d. h. bb und nn sind teilerfremd). Dann gilt: acmodna \equiv c \mod n
  15. Es gelte abmodxa \equiv b \mod x und acmodya \equiv c \mod y sowie n=ggT(x,y)n = \ggT(x,y). Daraus folgt: bcmodnb \equiv c \mod n
 
 

Seit die Mathematiker über die Relativitätstheorie hergefallen sind, verstehe ich sie selbst nicht mehr.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе