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.

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.

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

Also ist 6 das multiplikative Inverse zu 6 modulo 7.

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 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

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.

\((\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.

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\).