Zwei Zahlen a und b sind kongruent modulo m wenn a-b ein Vielfaches von m ist.

Zwei ganze Zahlen a und b sind kongruent modulo m genau dann, wenn sie bei Division durch m denselben Rest r haben. Das ist gleichbedeutend damit, dass sie sich um ein ganzzahliges Vielfaches von m unterscheiden (d.h. a-b=km mit \(k \in \mathbb{Z}\)):

Sei \(a = k_1 \cdot m + r\) und \(b = k_2 \cdot m + r\) mit \(k_1,\; k_2 \in \mathbb{Z}\). Dann ist \(a-b = k_1 \cdot m - k_2 \cdot m = (k_1 - k_2) \cdot m\).

Wir reduzieren zunächst alle Zahlen modulo 7:
22 = 1 mod 7
37 = 2 mod 7
80 = 3 mod 7
Somit 22x37 + 80 = 1x2 + 3 = 5 mod 7.

Natürlich kann man auch erst 22x37 + 80 = 894 ausrechnen und dann modulo 7 reduzieren, aber der andere Weg ist leichter, weil die Zahlen nicht so groß werden.

Wir reduzieren zunächst alle Zahlen modulo 9:
56 = 2 mod 9
101 = 2 mod 9
73 = 1 mod 9
Somit 56 + 101 x 73 = 2 + 2 x 1 = 4 mod 9.

6 + 1 = 7 = 0 mod 7

Also ist 1 das additive Inverse zu 6 modulo 7.

\(6 \cdot 6 = 36 = 1 \;mod \; 7\)

Also ist 6 das multiplikative Inverse zu 6 modulo 7.

3 und 6 sind nicht teilerfremd, daher gibt es kein multiplikatives Inverses zu 3 modulo 6.

\(\begin{tabular}{|c|c|} \hline a & 3a\; mod \;6\\ \hline 1 & 3\\ \hline 2 & 0\\ \hline 3 & 3\\ \hline 4 & 0\\ \hline 5 & 3\\ \hline \end{tabular} \)

x hat genau dann ein multiplikatives Inverses in \(\mathbb{Z}_6\), wenn x und 6 teilerfremd sind. Daher haben nur x=1 und x=5 ein multiplikatives Inverses modulo 6, und zwar jeweils sich selbst:

\(1 \cdot 1 = 1 \; mod\; 6\)  bzw.  \(5 \cdot 5 = 25 = 1\; mod\; 6\)

x hat genau dann ein multiplikatives Inverses in \(\mathbb{Z}_{10}\), wenn x und 10 teilerfremd sind. Das gilt für x=1, 3, 7 und 9.
Das multiplikative Inverse von 1 mod 10 ist 1 (denn 1x1 = 1 mod 10).
Das multiplikative Inverse von 3 mod 10 ist 7 (denn 3x7 = 21 = 1 mod 10). Umgekehrt ist also 3 das multiplikative Inverse von 7 mod 10.
Das multiplikative Inverse von 9 mod 10 ist 9 (denn 9x9 = 81 = 1 mod 10).

2x2 =  4 mod 7
2x3 =  6 mod 7
2x4 =  8 = 1 mod 7
2x5 = 10 = 3 mod 7
2x6 = 12 = 5 mod 7

3x3 =  9 = 2 mod 7
3x4 = 12 = 5 mod 7
3x5 = 15 = 1 mod 7
3x6 = 18 = 4 mod 7

4x4 = 16 = 2 mod 7
4x5 = 20 = 6 mod 7
4x6 = 24 = 3 mod 7

5x5 = 25 = 4 mod 7
5x6 = 30 = 2 mod 7

6x6 = 36 = 1 mod 7

2.2 = 4 = 0 mod 4
2.3 = 6 = 2 mod 4
3.3 = 9 = 1 mod 4

Die Gleichung hat die Form ax = b mod 8 mit a=4 und b=0. Weil ggT(a,8) = ggT(4,8) = 4 und 4 ein Teiler von b=0 ist, gibt es 4 Lösungen der Gleichung in \(\mathbb{Z}_8\), und zwar x = 0, 2, 4 und 6:

4x0 = 0 mod 8
4x2 = 8 = 0 mod 8
4x4 = 16 = 0 mod 8
4x6 = 24 = 0 mod 8

Die Gleichung hat die Form ax = b mod 6 mit a=4 und b=2. Weil ggT(a,6) = ggT(4,6) = 2 und 2 ein Teiler von b=2 ist, muss es 2 Lösungen der Gleichung in \(\mathbb{Z}_6\) geben.

Diese sind x=2 und x=5:
4x2 = 8 = 2 mod 6
4x5 = 20 = 2 mod 6

\(\mathbb{Z}_6 = \left\{ 0,1,2,3,4,5 \right\}\) ist die Menge aller Reste bei Division durch 6.
\(\mathbb{Z}^*_6 = \left\{ 1,5 \right\}\) ist die Menge aller Reste modulo 6, die ein multiplikatives Inverses haben. Diese müssen teilerfremd sein zu 6, was nur 1 und 5 erfüllen. \((\mathbb{Z}_6, \cdot)\) ist somit auch keine Gruppe, \((\mathbb{Z}^*_6, \cdot)\) dagegen schon (denn es sind ja per Definition nur Elemente darin enthalten, die auch ein multiplikatives Inverses haben, und das Assoziativgesetz gilt).

Nur die erste Aussage ist zutreffend: \((\mathbb{Z}_9,+)\) ist eine Gruppe (neutrales Element 0, Inverses 9-x für jedes x in \(\mathbb{Z}_9\), Assoziativgesetz gilt).

\((\mathbb{Z}_4, +)\) ist eine kommutative Gruppe (neutrales Element 0, inverses Element a' = 4-a für jedes a in \(\mathbb{Z}_4\), Assoziativgesetz gilt).
\((\mathbb{Z}^*_4, +)\) ist keine Gruppe, da das neutrale Element fehlt: \(0 \;\notin\; \mathbb{Z}^*_4 = \left\{ 1,3 \right\}\)
\((\mathbb{Z}_4, \cdot)\) ist keine Gruppe, da nicht jedes Element (z.B. 2) ein Inverses besitzt.
\((\mathbb{Z}^*_4, \cdot)\) ist eine kommutative Gruppe mit den Elementen \(\mathbb{Z}^*_4 = \left\{ 1,3 \right\}\): Neutrales Element 1, Inverse \(1^{-1} = 1\) und \(3^{-1} = 3\), Assoziativgesetz gilt.

Nur \((\mathbb{Z}_5, +, \cdot)\) ist ein Körper (allgemein jedes \(\mathbb{Z}_p\), wenn p eine Primzahl ist):

1. \((\mathbb{Z}_5, +)\) ist eine kommutative Gruppe mit neutralem Element 0.
2. \((\mathbb{Z}_5 \setminus \left\{0\right\}, \cdot) = (\mathbb{Z}^*_5, \cdot)\) ist eine kommutative Gruppe mit neutralem Element 1.
3. Das Distributivgesetz gilt: \(a \cdot (b+c) = a \cdot b + a \cdot c\) für alle a,b,c in \(\mathbb{Z}_5\)

Multiplikationstabelle für \(\mathbb{Z}_5\):
\(\begin{tabular}{c|ccccc} \cdot & 0 & 1 & 2 & 3 & 4\\ \hline 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3 & 4\\ 2 & 0 & 2 & 4 & 1 & 3\\ 3 & 0 & 3 & 1 & 4 & 2\\ 4 & 0 & 4 & 3 & 2 & 1\\ \end{tabular}\)

\((\mathbb{Z}_4, +)\) ist zwar eine Gruppe, \((\mathbb{Z}_4 \setminus \left\{0\right\},\cdot)\) jedoch nicht (Inverses fehlt für 2),
also kann \((\mathbb{Z}_4,+,\cdot)\) kein Körper sein.

\((\mathbb{Z}^*_4,\cdot)\) ist zwar eine Gruppe, \((\mathbb{Z}^*_4, +)\) jedoch nicht (\(1+3=0 \; \notin \; \mathbb{Z}^*_4\)), also kann \((\mathbb{Z}^*_4, +, \cdot)\) kein Körper sein.

\((\mathbb{Z}^*_5,\cdot)\) ist zwar eine Gruppe, \((\mathbb{Z}^*_5, +)\) jedoch nicht (\(1+4=0 \; \notin \; \mathbb{Z}^*_5\)), also kann \((\mathbb{Z}^*_5, +, \cdot)\) kein Körper sein.

Die drei Moduln sind teilerfremd, also können wir den Chinesischen Restsatz anwenden. Der Aufgabenstellung entnehmen wir:\(a_1 = 1,\; a_2 = 0,\; a_3 = 6 \\ m_1 = 2,\; m_2 = 3,\; m_3 = 7 \)

Daraus berechnen wir:
\(m = m_1 \cdot m_2 \cdot m_3 = 42\\ M_1 = m_2 \cdot m_3 = 21\\ M_2 = m_1 \cdot m_3 = 14\\ M_3 = m_1 \cdot m_2 = 6\)

Nun suchen wir das Inverse \(N_i = M_i^{-1} \; mod \; m_i\):

\(N_1 = 21^{-1} = 1^{-1} = 1 \; mod\; 2\\ N_2 = 14^{-1} = 2^{-1} = 2 \; mod\; 3\\ N_3 = 6^{-1} = 6 \; mod\; 7\)

Die Lösung lautet:

\(x = a_1 M_1 N_1 + a_2 M_2 N_2 + a_3 M_3 N_3 \;mod \;m = 1 \cdot 21 \cdot 1 + 0 \cdot 14 \cdot 2 + 6 \cdot 6 \cdot 6 = 237 = 27 \; mod \; 42\)

Die drei Moduln sind teilerfremd, also können wir den Chinesischen Restsatz anwenden. Der Aufgabenstellung entnehmen wir:
\(a_1 = 1,\; a_2 = a_3 = 2\\ m_1 = 2,\; m_2 = 3,\; m_3 = 5\)

Daraus berechnen wir:
\(m = m_1 \cdot m_2 \cdot m_3 = 30\\ M_1 = m_2 \cdot m_3 = 15\\ M_2 = m_1 \cdot m_3 = 10\\ M_3 = m_1 \cdot m_2 = 6\)

Nun suchen wir das Inverse \(N_i = M_i^{-1} \; mod \; m_i\):

\(N_1 = 15^{-1} = 1^{-1} = 1 \;mod \;2\\ N_2 = 10^{-1} = 1^{-1} = 1 \;mod \;3\\ N_3 = 6^{-1} = 1^{-1} = 1 \;mod \;5\)

Die Lösung lautet:

\(x = a_1 M_1 N_1 + a_2 M_2 N_2 + a_3 M_3 N_3 \;mod \;m = 1 \cdot 15 \cdot 1 + 2 \cdot 45 \cdot 1 + 6 \cdot 35 \cdot 8 = 15 + 20 + 12 = 47 = 17 \;mod \;30\)

Die drei Moduln sind teilerfremd, also können wir den Chinesischen Restsatz anwenden. Der Aufgabenstellung entnehmen wir:
\(a_1 = 4,\; a_2 = a_3 = 6\\ m_1 = 5,\; m_2 = 7,\; m_3 = 9\)

Daraus berechnen wir:
\(m = m_1 \cdot m_2 \cdot m_3 = 315\\ M_1 = m_2 \cdot m_3 = 63\\ M_2 = m_1 \cdot m_3 = 45\\ M_3 = m_1 \cdot m_2 = 35 \)

Nun suchen wir das Inverse \(N_i = M_i^{-1} \; mod \; m_i\):

\(N_1 = 63^{-1} = 3^{-1} = 2 \;mod \;5\\ N_2 = 45^{-1} = 3^{-1} = 5 \;mod \;7\\ N_3 = 35^{-1} = 8^{-1} = 8 \;mod \;9\)

Die Lösung lautet:

\(x = a_1 M_1 N_1 + a_2 M_2 N_2 + a_3 M_3 N_3 \;mod \;m = 4 \cdot 63 \cdot 2 + 6 \cdot 45 \cdot 5 + 6 \cdot 35 \cdot 8 = 504 + 1350 + 1680 = 189 + 90 + 105 = 384 = 69 \;mod \;315\)

Ein Polynom p(x) vom Grad deg(p)>1 ist irreduzibel genau dann, wenn es kein Polynom q(x) vom Grad 0 < deg(q) < deg(p) gibt, das p(x) teilt, d.h. wenn p(x) nur Konstanten c oder sich selbst als Teiler hat. Ein irreduzibles Polynom lässt sich also nicht als Produkt "einfacherer" Polynome schreiben. Die Irreduzibilität von Polynomen entspricht der Primzahleigenschaft bei ganzen Zahlen.

Ein Polynom vom Grad 2 (oder 3) ist irreduzibel über einem Körper \(\mathbb{K}\) genau dann, wenn es keine Nullstellen in \(\mathbb{K}\) hat. Wir suchen also die Nullstellen des Polynoms \(x^2 + x - 12\). Mit der p-q-Formel folgt \(x_{1,2} = -\frac{1}{2} \pm \frac{7}{2} = \left\{ 3, -4\right\} \in \mathbb{R}\). Somit ist \(x^2 + x - 12 = (x-3)(x+4)\). (x-3) und (x+4) sind (wie alle Polynome vom Grad 1) irreduzibel.

Ein Polynom vom Grad 2 (oder 3) ist irreduzibel über einem Körper \(\mathbb{K}\) genau dann, wenn es keine Nullstellen in \(\mathbb{K}\) hat. Wir suchen also die Nullstellen des Polynoms \(x^2 + 6x + 12\). Mit der p-q-Formel folgt \(x_{1,2} = -3 \pm \sqrt{-3} \; \notin \; \mathbb{R}\). Da man aus negativen Zahlen in \(\mathbb{R}\) keine Wurzel ziehen kann, hat das Polynom keine reellen Nullstellen. Somit ist \(x^2 + 6x + 12\) irreduzibel über \(\mathbb{R}\).

Es gibt genau dann einen Körper mit n Elementen, wenn \(n = p^k\) eine Primzahlpotenz ist. Das gilt für n = 2, n=7 und \(n=16 = 2^4\), nicht jedoch für n=22.

\(\varphi(3) = 2\), denn ggT(3,1) = ggT(3,2) = 1. Es gibt also 2 Zahlen zwischen 1 und 3, die teilerfremd zu 3 sind (ggT: größter gemeinsamer Teiler).

\(\varphi(6) = 2\), denn ggT(6,1) = ggT(6,5) = 1, ggT(6,2) = ggT(6,4) = 2 und ggT(6,3) = 3. Es gibt also 2 Zahlen zwischen 1 und 6, die teilerfremd zu 6 sind.

\(\varphi(8) = 4\), denn ggT(8,1) = ggT(8,3) = ggT(8,5) = ggT(8,7) = 1, ggT(8,2) = ggT(8,6) = 2 und ggT(8,4) = 4. Es gibt also 4 Zahlen zwischen 1 und 8, die teilerfremd zu 8 sind.

\(\varphi(10) = 4\), denn ggT(10,1) = ggT(10,3) = ggT(10,7) = ggT(10,9) = 1, ggT(10,2) = ggT(10,4) = ggT(10,6) = ggT(10,8) = 2 und ggT(10,5) = 5. Es gibt also 4 Zahlen zwischen 1 und 10, die teilerfremd zu 10 sind.

Die Ordnung von \( \mathbb{Z}^*_{11}\) ist 10 (denn 11 ist eine Primzahl), somit ist \(2^{10} = 1\; mod\; 11\). Es folgt: \(2^{22} = (2^{10})^2 \cdot 2^2 = 1 \cdot 2^2 = 4 \;mod \;11\)

Die Ordnung von \(\mathbb{Z}^*_{12}\) ist \(\varphi(12) = 4\), somit ist \(7^{4} = 1 \;mod \;12\). Es folgt: \(7^{24} = (7^{4})^6 = 1 \;mod \;12\)

Alternative Lösung (ohne Verwendung des Tipps): \(7^{24} = (7^2)^{12} = 49^{12} = 1^{12} = 1 \;mod \;12\)

Für jede Primzahl p ist \(\varphi(p) = p-1\), denn eine Primzahl hat nur 1 und sich selbst als Teiler. Somit ist ggT(p,1) = 1, ggT(p,p) = p und ggT(p,m) = 1 für alle ganzen Zahlen m mit \(1.

Sei \(a \in \left\{1,2,...,n \right\}\). Die Zahlen a und n = pq können nur dann gemeinsame Teiler haben, wenn a ein Vielfaches von p oder q ist, denn p und q sind Primzahlen (und haben somit selbst keine echten Teiler). Es gibt q Vielfache von p in \(\left\{1,2,...,n \right\}\), und zwar p, 2p, 3p,..., qp. Ebenso gibt es p Vielfache von q in \(\left\{1,2,...,n \right\}\), und zwar q, 2q, 3q,..., pq. Bis auf pq sind diese wegen \(p \neq q\) alle verschieden. Diese p+q Vielfachen müssen wir also von n abziehen, um die Anzahl der zu n teilerfremdem Zahlen zu ermitteln (und 1 addieren, da wir sonst den Kandidaten n=pq zweimal abziehen):

\(\varphi (n) = n - p - q +1 = pq-p-q+1 = (p-1)(q-1)\)

Wir schreiben die Potenz 99 in Binärdarstellung: \(99 = 64 + 32 + 2 + 1 = 2^6 + 2^5 + 2^1 + 2^0\)
Somit ist \(6^{99} = 6^{(2^6)} \cdot 6^{(2^5)} \cdot 6^{(2^1)} \cdot 6^{(2^0)} \;mod\; 100\).
Wir berechnen nun die einzelnen Faktoren modulo 100:

\(\begin{tabular}{r|rrrrrrr} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 2^i & 1 & 2 & 4 & 8 & 16 & 32 & 64\\ 6^{(2^i)} & 6 & 36 & -4 & 16 & 56 & 36 & -4\\ \end{tabular}\)

Somit ist \(6^{99} = 6 \cdot 36 \cdot 36 \cdot (-4) = 6 \cdot (-4) \cdot (-4) = 96 \;mod\; 100\).

Wir schreiben die Potenz 73 in Binärdarstellung: \(73 = 64 + 8 + 1 = 2^6 + 2^3 + 2^0\)
Somit ist \(19^{73} = 19^{(2^6)} \cdot 19^{(2^3)} \cdot 19^{(2^0)} \;mod\; 100\).
Wir berechnen die einzelnen Faktoren modulo 100:

\(\begin{tabular}{r|rrrrrrr} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 2^i & 1 & 2 & 4 & 8 & 16 & 32 & 64\\ 19^{(2^i)} & 19 & 61 & 21 & 41 & 81 & 61 & 21\\ \end{tabular}\)

Somit ist \(19^{73} = 19 \cdot 41 \cdot 21 = 59\;mod\; 100\).

Wir schreiben die Potenz 101 in Binärdarstellung: \(101 = 64 + 32 + 4 + 1 = 2^6 + 2^5 + 2^2 + 2^0\)
Somit ist \(77^{101} = 77^{(2^6)} \cdot 77^{(2^5)} \cdot 77^{(2^2)} \cdot 77^{(2^0)} \;mod\; 113\).
Wir berechnen die einzelnen Faktoren modulo 113:

\(\begin{tabular}{r|rrrrrrr} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 2^i & 1 & 2 & 4 & 8 & 16 & 32 & 64\\ 77^{(2^i)} & 77 & 53 & -16 & 30 & -4 & 16 & 30\\ \end{tabular}\)

Somit ist \(77^{101} = 77 \cdot (-16) \cdot 16 \cdot 30 = 82\;mod\; 113\).

Wir schreiben die Potenz 167 in Binärdarstellung: \(167 = 128 + 32 + 4 + 2 + 1 = 2^7 + 2^5 + 2^2 + 2^1 + 2^0\)
Somit ist \(43^{167} = 43^{(2^7)} \cdot 43^{(2^5)} \cdot 43^{(2^2)} \cdot 43^{(2^1)} \cdot 43^{(2^0)} \;mod \;113\).
Wir berechnen die einzelnen Faktoren modulo 113:

\(\begin{tabular}{r|rrrrrrrr} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline 2^i & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128\\ 43^{(2^i)} & 43 & 41 & -14 & -30 & -4 & 16 & 30 & -4\\ \end{tabular}\)

Somit ist \(43^{167} = 43 \cdot 41 \cdot (-14) \cdot 16 \cdot (-4) = 21\;mod\; 113\).

Ein Polynom p(x) ist irreduzibel genau dann, wenn es kein Polynom kleineren Grades gibt, das p(x) teilt.

\(x^4+x+1\) hat keine Nullstelle in \(\mathbb{Z}_2\) und lässt sich somit nicht in (irreduzible) Polynome vom Grad 1 bzw. 3 zerlegen. Ebensowenig lässt sich \(x^4+x+1\) in irreduzible Polynome vom Grad 2 zerlegen, wie diese Polynomdivision zeigt (siehe Bild):
\((x^4+x+1):(x^2+x+1) = x^2+x\); Rest 1 (da von den Poynomen 2. Grades nur \(x^2+x+1\) irreduzibel über \(\mathbb{Z}_2\) ist, müssen wir keine weiteren Polynome überprüfen). \(x^4+x+1\) ist somit irreduzibel über \(\mathbb{Z}_2\).

\(x^3+x^2+1\) und \(x^3+x+1\) haben keine Nullstelle in \(\mathbb{Z}_2\) und lassen sich also auch nicht in (irreduzible) Polynome vom Grad 1 bzw. 2 zerlegen. Beide Poynome sind somit irreduzibel.