Rechenregeln für Kongruenzen

Elementare Rechenregeln

Satz 164R (Eigenschaften von Kongruenzen)

1. $a \equiv a \mod{m}$ (Reflexivität)
2. Aus $a \equiv b \mod{m}$ folgt $b \equiv a \mod{m}$ (Symmetrie)
3. Aus $a \equiv b \mod{m}$ und $b \equiv c \mod{m}$ folgt $a \equiv c \mod{m}$ (Transitivität)
4. $na \equiv nb \mod{m}$
5. $a + c \equiv b + d \mod{m}$ $a - c \equiv b - d \mod{m}$
6. $ac \equiv bd \mod{m}$ $a^n \equiv b^n \mod{m}$

Beweis

Abgeleitete Rechenregeln

1. Für $t \ne 0$ gilt: $\qquad t \cdot a \equiv t \cdot b \mod |t| \cdot m$
2. Ist $k$ ein Teiler von $m$, dann gilt: $\qquad a \equiv b \mod k$
3. Sei $c \cdot a \equiv c \cdot b \mod n$ sowie $d = \ggT(c,n)$ (größter gemeinsamer Teiler), dann gilt: $a \equiv b \mod(n/d)$Sind $c$ und $n$ teilerfremd, also $d = 1$, dann folgt sofort $a \equiv b \mod n$
4. Sei $c \cdot a \equiv c \cdot b \mod p$ mit einer Primzahl $p$, wobei $p$ kein Teiler von $c$ ist. Dann gilt: $a \equiv b \mod p$
5. Sei $a \equiv b \mod n$ und $c > 0$. Dann gilt: $c \cdot a \equiv c \cdot b \mod(c \cdot n)$
6. Sei $a \equiv b \mod n$. Ferner sei $d > 0$ ein Teiler der ganzen Zahlen $a$, $b$. Dann gilt: $(a/d) \equiv (b/d) \mod(n/d)$
7. Für jede ungerade Zahl $a$ gilt $a^2 \equiv 1 \mod 8$Mit anderen Worten: Teilt man $a^2$ durch 8, dann bleibt als Rest 1.
8. Für jede ganze Zahl gilt entweder $a^3 \equiv 0 \mod 9$ oder $a^3 \equiv 1 \mod 9$ oder $a^3 \equiv 8 \mod 9$Mit anderen Worten: Entweder $a^3$ ist durch 9 teilbar oder es bleibt als Rest 1 oder 8.
9. Für jede ganze Zahl gilt entweder $a^3 \equiv 0 \mod 7$ oder $a^3 \equiv 1 \mod 7$ oder $a^3 \equiv 6 \mod 7$Mit anderen Worten: Entweder $a^3$ ist durch 7 teilbar oder es bleibt als Rest 1 oder 6.
10. Für jede ganze Zahl gilt entweder $a^4 \equiv 0 \mod 5$ oder $a^4 \equiv 1 \mod 5$Mit anderen Worten: Entweder $a^4$ ist durch 5 teilbar oder es bleibt als Rest 1
11. Ist $a$ sowohl eine Quadratzahl als auch eine Kubikzahl (z.B. $a = 64$) dann gilt entweder $a \equiv 0 \mod 36$ oder $a \equiv 1 \mod 36$ oder $a \equiv 9 \mod 36$ oder $a \equiv 28 \mod 36$
12. Sei $p$ eine Primzahl mit $n < p < 2n$. Dann gilt${\chooseNT {2n} n} \equiv 0 \mod{p}$
13. Sei $a$ eine ungerade ganze Zahl. Ferner sei $n > 0$. Dann gilt: $a^{2^n} \equiv 1 \mod 2^{n+2}$
14. Seien $a \cdot b \equiv c \cdot d \mod n$, $b \equiv d \mod n$ sowie $\ggT(b,n) = 1$ (d. h. $b$ und $n$ sind teilerfremd). Dann gilt: $a \equiv c \mod n$
15. Es gelte $a \equiv b \mod x$ und $a \equiv c \mod y$ sowie $n = \ggT(x,y)$. Daraus folgt: $b \equiv c \mod n$

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

Albert Einstein

Elementare Zahlentheorie

• Kongruenzen
  • Veranschaulichung
  • Rechenregeln
  • Beispiele
  • Weitere Beispiele
  • Chinesischer Restsatz
• Satz von Fermat
• Eulersche Phi-Funktion
• Diophantische Gleichungen
• Mehr über Primzahlen
• Goodstein-Folgen