Fragenliste von Elementare Zahlentheorie

Welche Zahlen sind kongruent modulo 3 ? Nr. 3871
	$3 \equiv 9 \pmod{3}$
	$4 \equiv 19 \pmod{3}$
	$5 \equiv 15 \pmod{3}$
	$6 \equiv 25 \pmod{3}$
	6:3= 2 Rest 0, 25:3= 8 Rest
Lösungsweg Zwei Zahlen a und b sind kongruent modulo m wenn a-b ein Vielfaches von m ist.

Welche dieser Mengen mit Verknüpfungen sind eine Gruppe? Nr. 3872
	$(\mathbb{Z}, \cdot)$
	$(\mathbb{Z}, +)$
	$(\mathbb{R}, \cdot)$
	$(\mathbb{R}\backslash \{0\}, \cdot)$

Welche Aussagen treffen für den Restklassenkörper $\mathbb {Z}_3$ zu? Nr. 3873
	2 ist das additive Inverse von 2
	2 ist das multiplikative Inverse von 2
	2 ist das additive Inverse von 1
	1 ist das additive Inverse von 1

Über die Menge {a,b,c} sei folgende Verknüpfung * definiert. Welche Aussagen treffen zu? $\begin{tabular}{\|c\|c\|c\|c\|} \hline *& a & b & c\\ \hline a & a & b & c\\ \hline b & b & c & a\\ \hline c & c & a & b\\ \hline \end{tabular}$ Nr. 4017
	Es gibt kein neutrales Element
	c ist das Inverse zu b
	Es handelt sich um eine Gruppe
	a ist das Inverse zu c

Über die Menge {a,b,c} sei folgende Verknüpfung * definiert. Welche Aussagen treffen zu?

$\begin{tabular}{|c|c|c|c|} \hline *& a & b & c\\ \hline a & b & c & a\\ \hline b & c & a & b\\ \hline c & a & b & c\\ \hline \end{tabular}$

Nr. 4018

Es gibt kein neutrales Element

Es handelt sich um eine Gruppe

b is das Inverse Element von c

Zwei ganze Zahlen a und b sind kongruent modulo m genau dann, wenn sie ... Nr. 4646
	sich um m unterscheiden (d.h. wenn a-b=m oder b-a=m gilt).
	bei Division durch m denselben Rest haben.
	sich um ein ganzzahliges Vielfaches von m unterscheiden (d.h. wenn a-b=km mit $k \in \mathbb{Z}$ gilt).
	teilbar sind durch m.
Lösungsweg 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$ .

Berechnen Sie $(22 \cdot 37 + 80) mod \; 7$ ! Nr. 4647
	2
	3
	5
	8
Lösungsweg 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.

Berechnen Sie $(56 + 101 \cdot 73) \; mod\; 9$ Nr. 4648
	1
	3
	4
	8
Lösungsweg 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.

Bestimmen Sie das additive Inverse zu 6 modulo 7! Nr. 4649
	0
	1
	2
	Es gibt kein additives Inverses zu 6 modulo 7.
Lösungsweg 6 + 1 = 7 = 0 mod 7 Also ist 1 das additive Inverse zu 6 modulo 7.

Bestimmen Sie das multiplikative Inverse zu 6 modulo 7! Nr. 4650
	1
	2
	6
	Es gibt kein multiplikatives Inverses zu 6 modulo 7.
Lösungsweg $6 \cdot 6 = 36 = 1 \;mod \; 7$ Also ist 6 das multiplikative Inverse zu 6 modulo 7.

Bestimmen Sie das multiplikative Inverse zu 3 modulo 6! Nr. 4651
	2
	4
	5
	Es gibt kein multiplikatives Inverses zu 3 modulo 6.
Lösungsweg 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}$

Welche Elemente aus $\mathbb{Z}_6$ (Menge aller Restklassen modulo 6) haben ein multiplikatives Inverses? Nr. 4652
	1
	2
	3
	4
	5
Lösungsweg 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$

Welche Elemente aus $\mathbb{Z}_{10}$ (Menge aller Restklassen modulo 10) haben ein multiplikatives Inverses? Nr. 4653
	3
	5
	6
	7
	9
Lösungsweg 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).

Welches ist die korrekte Multiplikationstabelle für $\mathbb{Z}_3$ ? Nr. 4658
	$\begin{tabular}{c\|ccc} \cdot & 0 & 1 & 2\\ \hline 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2\\ 2 & 0 & 2 & 1\\ \end{tabular}$
	$\begin{tabular}{c\|ccc} \cdot & 0 & 1 & 2\\ \hline 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2\\ 2 & 0 & 2 & 0\\ \end{tabular}$
	$\begin{tabular}{c\|ccc} \cdot & 0 & 1 & 2\\ \hline 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2\\ 2 & 0 & 2 & 2\\ \end{tabular}$
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 1 & 2\\ 3 & 0 & 3 & 2 & 1\\ \end{tabular}$

Welches ist die korrekte Multiplikationstabelle für $\mathbb{Z}_7$ ? (Hinweis: Die Zeilen und Spalten für 0 und 1 wurden aus Platzgründen weggelassen.) Nr. 4659
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 4 & 2\\ 6 & 5 & 4 & 3 & 2 & 1\\ \end{array}$
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 1 & 3\\ 6 & 5 & 4 & 3 & 3 & 4\\ \end{array}$
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 2 & 5\\ 6 & 5 & 4 & 3 & 5 & 3\\ \end{array}$
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 1 & 0\\ 6 & 5 & 4 & 3 & 0 & 7\\ \end{array}$
Lösungsweg 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

Welches ist die korrekte Multiplikationstabelle für $\mathbb{Z}_4$ ? Nr. 4660
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 0 & 1\\ 3 & 0 & 3 & 1 & 2\\ \end{tabular}$
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 0 & 2\\ 3 & 0 & 3 & 2 & 1\\ \end{tabular}$
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 1 & 3\\ 3 & 0 & 3 & 3 & 1\\ \end{tabular}$
Lösungsweg 2.2 = 4 = 0 mod 4 2.3 = 6 = 2 mod 4 3.3 = 9 = 1 mod 4

Wie viele Lösungen besitzt die Gleichung 4x = 0 mod 8 in $\mathbb{Z}_8$ ? Nr. 4661
	0
	1
	2
	4
Lösungsweg 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

Welche $x \in \mathbb{Z}_6$ lösen die Gleichung 4x = 2 mod 6? Nr. 4662
	2
	3
	4
	5
Lösungsweg 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

Welche Aussagen über $\mathbb{Z}_6$ bzw. $\mathbb{Z}^*_6$ treffen zu? Nr. 4663
	$\mathbb{Z}_6 = \left\{ 0,1,2,3,4,5 \right\}$
	$\mathbb{Z}^*_6 = \left\{ 1,3,5 \right\}$
	Nur 1 und 5 haben ein multiplikatives Inverses in $\mathbb{Z}_6$ .
	$(\mathbb{Z}_6, \cdot)$ ist eine Gruppe.
	$(\mathbb{Z}^*_6, \cdot)$ ist eine Gruppe.
Lösungsweg $\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).

Welche Aussagen über $\mathbb{Z}_9$ treffen zu? Nr. 4665
	$(\mathbb{Z}_9,+)$ ist eine Gruppe.
	$(\mathbb{Z}_9,\cdot)$ ist eine Gruppe.
	$(\mathbb{Z}_9,+)$ ist ein Ring.
	$(\mathbb{Z}_9,\cdot)$ ist ein Ring.
	$(\mathbb{Z}_9,+,\cdot)$ ist ein Körper.
Lösungsweg 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).

Welche dieser Mengen ist eine Gruppe? Nr. 4666
	$(\mathbb{Z}_4, +)$
	$(\mathbb{Z}^*_4, +)$
	$(\mathbb{Z}_4, \cdot)$
	$(\mathbb{Z}^*_4, \cdot)$
Lösungsweg $(\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.

Welche dieser Mengen ist ein Körper? Nr. 4667
	$(\mathbb{Z}_4, +, \cdot)$
	$(\mathbb{Z}^*_4, +, \cdot)$
	$(\mathbb{Z}_5, +, \cdot)$
	$(\mathbb{Z}^*_5, +, \cdot)$
Lösungsweg Nur $(\mathbb{Z}_5, +, \cdot)$ ist ein Körper (allgemein jedes $\mathbb{Z}_p$ , wenn p eine Primzahl ist): $(\mathbb{Z}_5, +)$ ist eine kommutative Gruppe mit neutralem Element 0. $(\mathbb{Z}_5 \setminus \left\{0\right\}, \cdot) = (\mathbb{Z}^_5, \cdot)$ ist eine kommutative Gruppe mit neutralem Element 1. 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.

Lösen Sie folgendes System von Kongruenzen mithilfe des Chinesischen Restsatzes: x = 1 mod 2; x = 0 mod 3; x = 6 mod 7 Nr. 4675
	9
	15
	21
	27
Lösungsweg 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$

Lösen Sie folgendes System von Kongruenzen mithilfe des Chinesischen Restsatzes: x = 1 mod 2; x = 2 mod 3; x = 2 mod 5 Nr. 4676
	17
	29
	37
	47
Lösungsweg 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$

Lösen Sie folgendes System von Kongruenzen mithilfe des Chinesischen Restsatzes: x = 4 mod 5; x = 6 mod 7; x = 6 mod 9 Nr. 4677
	219
	199
	97
	69
Lösungsweg 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$

Wann ist ein Polynom p(x) vom Grad deg(p)>1 irreduzibel? Nr. 4686
	Wenn alle Koeffizienten von p(x) Primzahlen sind.
	Wenn es kein Polynom q(x) vom Grad 0 < deg(q) < deg(p) gibt, das p(x) teilt.
	Wenn der größte gemeinsame Teiler der Koeffizienten von p(x) 1 ist.
	Wenn p(x) nur Polynome der Form $x \pm q$ mit einer Primzahl q als Teiler hat.
	Wenn p(x) nur konstante Polynome c(x) = c oder sich selbst als Teiler hat.
Lösungsweg 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.

Zerlegen Sie $x^2 + x - 12$ über $\mathbb{R}$ in irreduzible Faktoren! Nr. 4688
	$x^2 + x - 12$ ist bereits irreduzibel über $\mathbb{R}$ .
	$x^2 + x - 12 = 1 \cdot (x^2 + x - 12)$
	$x^2 + x - 12 = (x+3)\cdot(x-4)$
	$x^2 + x - 12 = (x-3)\cdot(x+4)$
Lösungsweg 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.

Zerlegen Sie $x^2 + 6x + 12$ über $\mathbb{R}$ in irreduzible Faktoren! Nr. 4689
	$x^2 + 6x + 12$ ist bereits irreduzibel über $\mathbb{R}$ .
	$x^2 + 6x + 12 = (x+2)\cdot(x+6)$
	$x^2 + 6x + 12 = (x-2)\cdot(x-6)$
	$x^2 + 6x + 12 = (x+3)\cdot(x+4)$
Lösungsweg 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}$ .

Welche Aussagen treffen zu? Es gibt einen Körper mit ... Nr. 4690
	2 Elementen.
	7 Elementen.
	16 Elementen.
	22 Elementen.
Lösungsweg 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.

Die Eulersche $\varphi$ -Funktion ordnet jeder natürlichen Zahl n die Anzahl derjenigen Zahlen aus $\left\{1,2,...,n \right\}$ zu, die teilerfremd zu n sind. Welche Aussagen über die Phi-Funktion treffen zu? Nr. 4697
	$\varphi(3) = 2$
	$\varphi(6) = 2$
	$\varphi(8) = 3$
	$\varphi(10) = 4$
Lösungsweg $\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.

Berechnen Sie $2^{22} \;mod \;11$ ohne Taschenrechner! (Tipp: In einer Gruppe G gilt $g^{\|G\|} = 1$ für jedes Gruppenelement g.) Nr. 4703
	1
	2
	4
	8
Lösungsweg 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$

Berechnen Sie $7^{24} \;mod \;12$ ohne Taschenrechner! (Tipp: In einer Gruppe G gilt $g^{\|G\|} = 1$ für jedes Gruppenelement g.) Nr. 4704
	1
	2
	3
	4
Lösungsweg 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$

Die Eulersche $\varphi$ -Funktion ordnet jeder natürlichen Zahl n die Anzahl der Zahlen aus $\left\{1,2,...,n \right\}$ zu, die teilerfremd zu n sind. Was gilt im Falle einer Primzahl n=p? Nr. 4711
	$\varphi(p) = p$
	$\varphi(p) = p-1$
	$\varphi(p) = p-2$
	$\varphi(p) = (p-1)/2$
Lösungsweg 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<m<p$ .

Die Eulersche $\varphi$ -Funktion ordnet jeder natürlichen Zahl n die Anzahl der Zahlen aus $\left\{1,2,...,n \right\}$ zu, die teilerfremd zu n sind. Ist $n=p\cdot q$ ein Produkt zweier verschiedener Primzahlen, so gilt: Nr. 4712
	$\varphi (pq) = pq-1$
	$\varphi (pq) = p+q-1$
	$\varphi (pq) = (p-1)(q-1)$
Lösungsweg 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)$

Berechnen Sie $6^{99}\; mod \; 100$ durch schnelle Exponentiation! Nr. 4720
	16
	36
	56
	96
Lösungsweg 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$ .

Berechnen Sie $19^{73}\; mod\; 100$ durch schnelle Exponentiation! Nr. 4721
	39
	49
	59
	69
Lösungsweg 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$ .

Berechnen Sie $77^{101} \;mod\; 113$ durch schnelle Exponentiation! Nr. 4722
	97
	13
	59
	82
Lösungsweg 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$ .

Berechnen Sie $43^{167} \;mod\; 113$ durch schnelle Exponentiation! Nr. 4723
	17
	49
	21
	97
Lösungsweg 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$ .

Welche dieser Polynome sind irreduzibel über $\mathbb{Z}_2$ ? Nr. 4724
	$x^4+x^2+1$
	$x^4+x+1$
	$x^3+x^2+x+1$
	$x^3+x^2+1$
	$x^3+x+1$
Lösungsweg 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.

Anmelden

Passwort vergessen
Registrieren

NEWS

Die Mathe Plattform des Technikum Wien gewinnt den eLearning Award 2019 als Projekt des Jahres in der Kategorie Hochschule.

Festigen Sie Ihre Grundkenntnisse und bereiten Sie sich auf Prüfungen vor.
Im Juli starten wieder die Warm-up Kurse - ein kostenloser Service für Aufgenommene und Studierende der FHTW.

Mathematik, Physik, Elektrotechnik, Informatik, Englisch und Deutsch in kompakten Kursen, geblockt bis September.

Anmeldung und Informationen
Warm-up-Kurse

Die Plattform wächst! Wir bauen im Moment den Bereich des Studienwissens aus. Bitte haben Sie Verständnis, dass die Inhalte dort erst nach und nach ergänzt werden. Ebenso kann es bei Design und Grafik noch zu Änderungen, Verbesserungen und kleinen Bugs kommen. Danke für Ihr Verständnis!

weitere News

Wussten Sie schon?

Sie können sich rechts oben einen kostenlosen Benutzer erstellen. Dann wird Ihr Lernfortschritt gespeichert, Sie können Tests zwischenspeichern und an Tutorien teilnehmen.

Welches ist die korrekte Multiplikationstabelle für $\mathbb{Z}_3$ ? Nr. 4658
	$\begin{tabular}{c\|ccc} \cdot & 0 & 1 & 2\\ \hline 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2\\ 2 & 0 & 2 & 1\\ \end{tabular}$
	$\begin{tabular}{c\|ccc} \cdot & 0 & 1 & 2\\ \hline 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2\\ 2 & 0 & 2 & 0\\ \end{tabular}$
	$\begin{tabular}{c\|ccc} \cdot & 0 & 1 & 2\\ \hline 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2\\ 2 & 0 & 2 & 2\\ \end{tabular}$
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 1 & 2\\ 3 & 0 & 3 & 2 & 1\\ \end{tabular}$

Welches ist die korrekte Multiplikationstabelle für $\mathbb{Z}_7$ ? (Hinweis: Die Zeilen und Spalten für 0 und 1 wurden aus Platzgründen weggelassen.) Nr. 4659
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 4 & 2\\ 6 & 5 & 4 & 3 & 2 & 1\\ \end{array}$
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 1 & 3\\ 6 & 5 & 4 & 3 & 3 & 4\\ \end{array}$
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 2 & 5\\ 6 & 5 & 4 & 3 & 5 & 3\\ \end{array}$
	$\begin{array}{c\|ccccc} \cdot & 2 & 3 & 4 & 5 & 6\\ \hline 2 & 4 & 6 & 1 & 3 & 5\\ 3 & 6 & 2 & 5 & 1 & 4\\ 4 & 1 & 5 & 2 & 6 & 3\\ 5 & 3 & 1 & 6 & 1 & 0\\ 6 & 5 & 4 & 3 & 0 & 7\\ \end{array}$
Lösungsweg 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

Welches ist die korrekte Multiplikationstabelle für $\mathbb{Z}_4$ ? Nr. 4660
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 0 & 1\\ 3 & 0 & 3 & 1 & 2\\ \end{tabular}$
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 0 & 2\\ 3 & 0 & 3 & 2 & 1\\ \end{tabular}$
	$\begin{tabular}{c\|cccc} \cdot & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3\\ 2 & 0 & 2 & 1 & 3\\ 3 & 0 & 3 & 3 & 1\\ \end{tabular}$
Lösungsweg 2.2 = 4 = 0 mod 4 2.3 = 6 = 2 mod 4 3.3 = 9 = 1 mod 4

Mathematik Übungsplattform

Fragenliste von Elementare Zahlentheorie

Anmelden

NEWS