Modulare Arithmetik
Unter der Bedingung \( x, y, m \in \mathbb{Z} \) und \( m > 1 \) ist die durch
\[
\beta = \{ (x, y) : m \mid (x – y) \}
\]
\[
\beta = \{ (x,y) : \text{die Differenz } x – y \text{ ist durch } m \text{ ohne Rest teilbar} \}
\]
definierte Relation eine Äquivalenzrelation.
Da in der Relation \(\beta\) die Differenz \( x – y \) durch \( m \) ohne Rest teilbar ist, gilt für ein \( k \in \mathbb{Z} \):
\[
x – y = m \cdot k \Rightarrow x = mk + y
\]
Da hierbei \( (x, y) \in \beta \) gilt und \( \beta \) eine Äquivalenzrelation ist, ist \( x \) kongruent zu \( y \).
Folglich ist für alle \( \forall x \in \mathbb{Z} \) die Zahl \( x \) kongruent zu dem Rest \( y \), den man bei der Division von \( x \) durch \( m \) erhält.
Diese Beziehung wird als
\[
x \equiv y \pmod{m}
\]
geschrieben und als „\( x \) ist kongruent zu \( y \) modulo \( m \)„ gelesen.
Hinweis:
\[
x \equiv y \pmod{m} \iff x = mk + y \iff \frac{x – y}{m} = k, \quad k \in \mathbb{Z}
\]
Beispiel:
Wir wollen \( x \) bestimmen, wenn \( 120 \equiv x \pmod{7} \) gegeben ist.
\[
120 \equiv x \pmod{7} \Rightarrow 120 \div 7
\]
\[
120= 17 \cdot 7 + 1 , \quad \text{Quotient: } 17, \quad \text{Rest: } 1
\]
\[
\Rightarrow x = 1
\]
\[
\text{woraus folgt } 120 \equiv 1 \pmod{7}
\]
\[
x = 1 + 7k, \quad k \in \mathbb{Z}
\]
\[
\text{Somit ergibt sich } x \in \{ \dots, -6, 1, 8, \dots \}.
\]
Beispiele:
\(
\bullet
\)
\[
\begin{array}{r|l}
48 & 5 \\
45 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 9 \\
3 &
\end{array}
\quad \Rightarrow \quad 48 \equiv 3 \pmod{5}
\]
\(
\bullet
\)
\[
\begin{array}{r|l}
48 & 5 \\
35 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 7 \\
13 &
\end{array}
\quad \Rightarrow \quad 48 \equiv 13 \pmod{5}
\]
\(
\bullet
\)
\[
\begin{array}{r|l}
48 & 5 \\
50 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 10 \\
-2 &
\end{array}
\quad \Rightarrow \quad 48 \equiv -2 \pmod{5}
\]
Beispiele:
\(
\bullet \quad 25 \equiv 4 \pmod{7} \quad \Rightarrow \quad \frac{25 – 4}{7} = 3, \quad 3 \in \mathbb{Z}
\)
\(
\bullet \quad 25 \equiv 39 \pmod{7} \quad \Rightarrow \quad \frac{25 – 39}{7} = -2, \quad -2 \in \mathbb{Z}
\)
\(
\bullet \quad 25 \equiv 11 \pmod{7} \quad \Rightarrow \quad \frac{25 – 11}{7} = 2, \quad 2 \in \mathbb{Z}
\)
Beispiel:
Wir wollen die Werte bestimmen, die \( x \) annehmen kann, wenn gilt:
\[
7x + 19 \equiv x – 2 \pmod{x}
\]
\[
\frac{7x + 19 – (x – 2)}{x} = k \quad \Rightarrow \quad \frac{6x + 21}{x} = k
\]
\[
\Rightarrow 6 + \frac{21}{x} = k
\]
Da \( x > 1 \), \( x \in \mathbb{Z} \) und \( k \in \mathbb{Z} \) sind, lautet die Menge der möglichen Werte für \( x \):
\[
\{ 3, 7, 21 \}
\]
AUFGABE 1
Wenn gilt:
\[
x^2 + 7x \equiv 15 \pmod{x}
\]
wie viele verschiedene Werte kann \( x \) dann annehmen?
\[
\text{A) 1} \quad \text{B) 2} \quad \text{C) 3} \quad \text{D) 4} \quad \text{E) 5}
\]
Lösung:
\[
x^2 + 7x \equiv 15 \pmod{x} \Rightarrow \frac{x^2 + 7x – 15}{x} = k
\]
\[
\Rightarrow x + 7 – \frac{15}{x} = k
\]
Da \( x > 1 \), \( x \in \mathbb{Z} \) und \( k \in \mathbb{Z} \) sind, ist die Menge der möglichen Werte für \( x \):
\[
\{ 3, 5, 15 \}
\]
\(\textbf{Antwort: C} \)
AUFGABE 2
Gegeben sei \( x^3 + x \equiv 2x^2 + 2 \pmod{(x^3 + x)} \). Wie groß is die Summe aller Werte, die \( x \) annehmen kann?
\[
\text{A) 3} \quad \text{B) 4} \quad \text{C) 5} \quad \text{D) 6} \quad \text{E) 7}
\]
Lösung:
\[
x^3 + x \equiv 2x^2 + 2 \pmod{(x^3 + x)}
\]
\[
\Rightarrow \frac{x^3 + x – (2x^2 + 2)}{x^3 + x} = k
\]
\[
\Rightarrow \frac{(x^2 + 1)(x – 2)}{x (x^2 + 1)} = k
\]
\[
\Rightarrow \frac{x – 2}{x} = k \Rightarrow 1 – \frac{2}{x} = k
\]
Da \( x^3 + x > 1 \), \( x \in \mathbb{Z} \) und \( k \in \mathbb{Z} \) gelten, sind die möglichen Werte für \( x \) gleich \( x_1 = 1, x_2 = 2 \).
\[
\Rightarrow x_1 + x_2 = 3
\]
\(\textbf{Antwort: A} \)
Restklassen:
Wir wissen, dass die auf der Menge der ganzen Zahlen definierte Äquivalenzrelation
\[
\beta = \{ (x, y) \mid \text{die Differenz } x – y \text{ ist durch } m \text{ ohne Rest teilbar} \}
\]
die Menge der ganzen Zahlen in Äquivalenzklassen unterteilt. Diese Äquivalenzklassen werden als
\[
\overline{0}, \overline{1}, \overline{2}, \dots, \overline{m-1}
\]
bezeichnet. Die Menge dieser Äquivalenzklassen heißt die Menge der Restklassen modulo \( m \) und wird als \( \mathbb{Z}/m \) dargestellt. Demnach gilt:
\[
\mathbb{Z} / m = \{ \overline{0}, \overline{1}, \overline{2}, \dots, \overline{m-1} \}
\]
Beispiel:
Für \( m = 5 \) wollen wir die Äquivalenzklassen der Relation \( \beta = \{ (x, y) : 5 \mid (x – y) \} \) bestimmen.
Die Menge der Restklassen lautet:
\[
\mathbb{Z} / 5 = \{ \overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4} \}
\]
Die einzelnen Klassen sind:
\[
\overline{0} = \{ \dots, -15, -10, -5, 0, 5, 10, 15, \dots \}
\]
\[
\overline{1} = \{ \dots, -14, -9, -4, 1, 6, 11, 16, \dots \}
\]
\[
\overline{2} = \{ \dots, -13, -8, -3, 2, 7, 12, 17, \dots \}
\]
\[
\overline{3} = \{ \dots, -12, -7, -2, 3, 8, 13, 18, \dots \}
\]
\[
\overline{4} = \{ \dots, -11, -6, -1, 4, 9, 14, 19, \dots \}
\]
In \( \mathbb{Z} / 5 \) sind alle Elemente innerhalb einer bestimmten Restklasse modulo 5 zueinander kongruent.
Für \( -11, 9 \in \overline{4} \) gilt beispielsweise:
\[
5 \mid (-11 – 9) \Rightarrow 5 \mid (-20) \Rightarrow -11 \equiv 9 \pmod{5}
\]
Zudem entspricht der Rest, der bei der Division einer beliebigen Zahl aus einer Äquivalenzklasse durch 5 entsteht, genau dem Repräsentanten dieser Restklasse.
Für \( -11, 14, 19 \in \overline{4} \) gilt:
\[
\begin{array}{r|l}
-11 & 5 \\
-15 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & -3 \\
4 &
\end{array}
\quad \quad
\begin{array}{r|l}
14& 5 \\
10& \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & 2 \\
4 &
\end{array}
\quad \quad
\begin{array}{r|l}
19& 5 \\
15& \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & 3 \\
4 &
\end{array}
\]
Hinweis:
Die standardmäßigen Repräsentanten der Restklassen in \( \mathbb{Z} / m \) sind die Zahlen \( 0, 1, 2, 3, \dots, m – 1 \).
Eigenschaften:
Für \( x, y, a, b, m \in \mathbb{Z} \) und \( m > 1 \) gilt:
1) Es seien \( x \equiv y \pmod{m} \) und \( a \equiv b \pmod{m} \).
Kongruenzen bezüglich desselben Moduls dürfen gliedweise addiert, subtrahiert oder multipliziert werden. Eine Division ist jedoch im Allgemeinen nicht zulässig.
\[
\begin{aligned}
x + a &\equiv y + b \pmod{m} \\
x – a &\equiv y – b \pmod{m} \\
x \cdot a &\equiv y \cdot b \pmod{m}
\end{aligned}
\]
Beispiele:
Gegeben sind \( 7 \equiv 19 \pmod{6} \) und \( 20 \equiv 2 \pmod{6} \).
\( \bullet \quad 7 + 20 \equiv 19 + 2 \pmod{6} \Rightarrow 27 \equiv 21 \pmod{6} \)
\( \bullet \quad 7 – 20 \equiv 19 – 2 \pmod{6} \Rightarrow -13 \equiv 17 \pmod{6} \)
\( \bullet \quad 7 \cdot 20 \equiv 19 \cdot 2 \pmod{6} \Rightarrow 140 \equiv 38 \pmod{6} \)
Folgerung:
Für \( \bar{p}, \bar{q} \in \mathbb{Z}/m \) gilt:
\[ \bar{p} + \bar{q} = \overline { p \;+ \; q } \]
\[ \bar{p} \cdot \bar{q} = \overline{p \;\cdot\; q} \]
Beispiele:
In \( \mathbb{Z}/5 \):
\[
\bar{3} + \bar{4} \equiv \overline{3 + 4 } \equiv 2
\]
\[
\bar{3} \cdot \bar{4} \equiv \overline{3 \cdot 4 } \equiv 2
\]
\[
\bar{1} +\bar{ 2 }+ \bar{3 } \equiv \overline{ 1 + 2 + 3 } \equiv 1
\]
2) Zu beiden Seiten einer Kongruenz darf eine beliebige ganze Zahl \( c \in \mathbb{Z} \) addiert oder davon subtrahiert werden.
\[
x \equiv y \pmod{m} \Rightarrow x + c \equiv y + c \pmod{m}
\]
\[
\Rightarrow x – c \equiv y – c \pmod{m}
\]
Beispiele:
\( \bullet \quad 27 \equiv 3 \pmod{8} \Rightarrow 27 + 5 \equiv 3 + 5 \pmod{8} \Rightarrow 32 \equiv 8 \pmod{8}
\)
\( \bullet \quad 27 \equiv 3 \pmod{8} \Rightarrow 27 – 3 \equiv 3 – 3 \pmod{8} \Rightarrow 24 \equiv 0 \pmod{8} \)
3) Beide Seiten einer Kongruenz dürfen mit einer ganzen Zahl \( c \in \mathbb{Z} \) multipliziert werden.
\[
x \equiv y \pmod{m} \Rightarrow x \cdot c \equiv y \cdot c \pmod{m}
\]
Beispiel:
\( \bullet \quad 25 \equiv 1 \pmod{4} \Rightarrow 25 \cdot 3 \equiv 1 \cdot 3 \pmod{4} \Rightarrow 75 \equiv 3 \pmod{4} \)
4) Division beider Seiten einer Kongruenz durch eine ganze Zahl \( c \in \mathbb{Z} \):
a) Wenn \( c \) und der Modul \( m \) teilerfremd sind, dürfen beide Seiten der Kongruenz durch \( c \) dividiert werden.
\[x \equiv y \pmod{m} \Rightarrow \frac{x}{c} \equiv \frac{y}{c} \pmod{m} \]
Beispiele:
\( \bullet \quad \) \[\Rightarrow 66 \equiv 3 \pmod{7} \Rightarrow \frac{66}{-3} \equiv \frac{3}{-3} \pmod{7} \Rightarrow -22 \equiv -1 \pmod{7} \]
\( \bullet \quad \) \[
\Rightarrow 58 \equiv 22 \pmod{9} \Rightarrow \frac{58}{2} \equiv \frac{22}{2} \pmod{9} \Rightarrow 29 \equiv 11 \pmod{9}
\]
\( \bullet \quad 40 \equiv 10 \pmod{6} \) In dieser Kongruenz dürfen wir beide Seiten nicht durch 10 kürzen. Denn die Zahl, durch die wir kürzen wollen (10), und der Modul (6) sind nicht teilerfremd (\(\text{ggT}(10,6) = 2 \neq 1\)). In diesem Fall gilt also:
\[
\frac{40}{10} \not\equiv \frac{10}{10} \pmod{6}
\]
\[
\Rightarrow 4 \not\equiv 1 \pmod{6}
[/]
b) Wenn \( c \) der größte gemeinsame Teiler der Zahlen \( x, y \) und des Moduls \( m \) ist, gilt:
\[
x \equiv y \pmod{m} \Rightarrow \frac{x}{c} \equiv \frac{y}{c} \pmod{\frac{m}{c}}
\]
Beispiel:
\( \bullet \quad 40 \equiv 10 \pmod{6} \Rightarrow \frac{40}{2} \equiv \frac{10}{2} \pmod{\frac{6}{2}} \Rightarrow 20 \equiv 5 \pmod{3}
\)
Da hierbei 20 und 3 sowie 5 und 3 teilerfremd sind, können wir weiter durch 5 dividieren:
\[
\frac{20}{5} \equiv \frac{5}{5} \pmod{3}
\]
\[
\Rightarrow 4 \equiv 1 \pmod{3}
\]
5) Beide Seiten einer Kongruenz dürfen mit einer positiven ganzen Zahl \( n \in \mathbb{Z}^+ \) potenziert werden.
\[
x \equiv y \pmod{m} \Rightarrow x^n \equiv y^n \pmod{m}
\]
Beispiel:
\[
96 \equiv 5 \pmod{7} \Rightarrow (96)^{10} \equiv 5^{10} \pmod{7}
\]
Hinweis:
Bei mathematischen Operationen in \( \mathbb{Z}/m \) kann eine Zahl \( a \) jederzeit durch \( a + mk \) (\( k \in \mathbb{Z} \)) ersetzt werden (dies gilt jedoch nicht für die Exponenten!). Das bedeutet, dass ganzzahlige Vielfache des Moduls addiert oder subtrahiert werden dürfen.
Beispiele:
In \( \mathbb{Z} / 5 \):
\( \bullet \quad 3 \cdot 4 + 3^4 + 4^3 \cdot 3 = 2 + 1 + 4 \cdot 3 = 2 + 1 + 2 = 0 \)
\( \bullet \quad (2x + 3) \cdot (x + 4) = 2x^2 + 2 \cdot 4x + 3x + 3 \cdot 4 = 2x^2 + (3 + 3)x + 2\)
\[
\quad = 2x^2 + x + 2
\]
\( \bullet \quad f(x) = 3x + 4 \Rightarrow (f \circ f)(x) = f(f(x)) \)
\[
\quad = 3 \cdot (3x + 4) + 4 = 3 \cdot 3x + 3 \cdot 4 + 4
\]
\[
\quad = 4x + 2 + 4
\]
\[
\quad = 4x + 1
\]
Beispiel:
Wir wollen das inverse Element bezüglich der Addition und der Multiplikation für die Zahl 3 in \( \mathbb{Z} / 7 \) finden.
Es sei \( x \) das additive Inverse von 3 und \( y \) das multiplikative Inverse von 3.
\[
3 + x = 0
\]
\[
\Rightarrow 3 + 4 + x = 0 + 4
\]
\[
\Rightarrow x = 4
\]
\[
3 \cdot y = 1 \Rightarrow 5 \cdot 3y = 5 \cdot 1
\]
\[
\Rightarrow 1 \cdot y = 5
\]
\[
\Rightarrow y = 5
\]
Hinweis:
In \( \mathbb{Z}/m \) bezeichnen wir das inverse Element eines Elements \( x \) bezüglich der Addition mit \( -x \) und das inverse Element bezüglich der Multiplikation (sofern es existiert) mit \( x^{-1} = \frac{1}{x} \). Für zwei beliebige Elemente \( x, y \) definieren wir die Division wie folgt:
\[
\frac{y}{x} = y \cdot \frac{1}{x}
\]
Beispiel:
In \( \mathbb{Z} / 5 \) betrachten wir folgende Rechnung:
\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]
Wir wollen das Ergebnis bestimmen.
\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]
\[
= (3 \cdot 2^{-1})^3 + (3^{-1})^5 + (-4)^{100}
\]
Hierbei gilt:
\( \bullet \quad 2^{-1} = x \), wobei \( x \) das multiplikative Inverse von 2 ist.
\( \bullet \quad 3^{-1} = y \), wobei \( y \) das multiplikative Inverse von 3 ist.
\( \bullet \quad -4 = z \), wobei \( z \) das additive Inverse von 4 ist.
Daraus folgt:
\[
2x = 1 \Rightarrow 3 \cdot 2x = 3 \cdot 1
\]
\[
\Rightarrow x = 3
\]
\[
3y = 1 \Rightarrow 2 \cdot 3y = 2 \cdot 1 \Rightarrow y = 2
\]
\[
4 + z = 0 \Rightarrow z = 1
\]
Setzen wir diese Werte ein:
\[
A = (3 \cdot 3)^3 + 2^5 + 1^{100}
\]
\[
= 4^3 + 2 + 1
\]
\[
= 4 + 2 + 1 = 2
\]
Beispiel:
Wir wollen die obige Aufgabe auf einem zweiten Weg lösen. Bei Rechnungen in \( \mathbb{Z} / 5 \) können wir zu den Zahlen Vielfache von 5 addieren oder davon subtrahieren, um die Brüche direkt teilbar zu machen.
\[
\text{In } \mathbb{Z} / 5 \text{ gilt:}
\]
\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]
\[
= \left( \frac{3 + 5}{2} \right)^3 + \left( \frac{1 + 5}{3} \right)^5 + (-4 + 5)^{100}
\]
\[
= 4^3 + 2^5 + 1^{100}
\]
\[
= 4 + 2 + 1 = 2
\]
Beispiel:
\[
\text{In } \mathbb{Z} / 7 \text{ gilt:}
\]
\[
\text{Wir berechnen das Ergebnis von: } (-5)^5 + (5^{-1})^3 + \left( \frac{1}{2} \right)^4
\]
\[
(-5)^5 + (5^{-1})^3 + \left( \frac{1}{2} \right)^4
\]
\[
= (-5 + 7)^5 + \left( \frac{1}{5} \right)^3 + \left( \frac{1+7}{2} \right)^4
\]
\[
= 2^5 + \left( \frac{1 + 7 + 7}{5} \right)^3 + 4^4
\]
\[
= 4 + 3^3 + 4
\]
\[
= 4 + 6 + 4 = 0
\]
Hinweis:
Die Lösung einer Gleichung der Form \( x^n = a \) in \( \mathbb{Z}/m \) wird symbolisch als
\[
x = \sqrt[n]{a}
\]
dargestellt.
Beispiel:
\[
\text{In } \mathbb{Z} / 7 \text{ betrachten wir:}
\]
\[ \quad \sqrt{2}, \quad \sqrt{1} \quad \text{und } \quad \sqrt[3]{6} \quad \]
\( \bullet \quad \sqrt{2} = \sqrt{2 + 7} = 3 \quad \text{und} \quad \sqrt{2} = \sqrt{2 + 2 \cdot 7} = 4 \)
\( \bullet \quad \sqrt{1} = 1 \quad \text{und} \quad \sqrt{1} = \sqrt{1 + 5 \cdot 7} = 6 \)
\( \bullet \quad \sqrt[3]{6} = \sqrt[3]{6 + 3 \cdot 7} = 3 \quad \text{und} \quad \sqrt[3]{6} = \sqrt[3]{6 – 7} = -1 = 6 \)
\[ \text{sowie } \sqrt[3]{6} = \sqrt[3]{6 – 2 \cdot 7} = \sqrt[3]{-8} = -2 = 5 \]
Alternativ lassen sich \( \sqrt{1} \) und \( \sqrt{2} \) auch direkt aus der Multiplikationstabelle in \( \mathbb{Z} / 7 \) ablesen. Auf der Hauptdiagonale befinden sich die Quadratzahlen, deren Wurzeln gesucht sind.
\[
\begin{array}{c|ccccccc}
\cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & \fbox{1} & 2 & 3 & 4 & 5 & 6 \\
2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\
3 & 0 & 3 & 6 & \fbox{2} & 5 & 1 & 4 \\
4 & 0 & 4 & 1 & 5 & \fbox{2} & 6 & 3 \\
5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\
6 & 0 & 6 & 5 & 4 & 3 & 2 & \fbox{1} \\
\end{array}
\]
\[
\sqrt{2} = \sqrt{3 \cdot 3} = 3
\]
\[
\sqrt{2} = \sqrt{4 \cdot 4 } = 4
\]
\[
\sqrt{1} = \sqrt{1 \cdot 1 } = 1
\]
\[
\sqrt{1} = \sqrt{6 \cdot 6 } = 6
\]
Beispiel:
\[
\text{In } \mathbb{Z} / 6 \text{ ist}
\]
\[
f(x) = 5x + 4 \text{ gegeben. Wir bestimmen die Umkehrfunktion } f^{-1}(x).
\]
\[
y = f(x) = 5x + 4 \Rightarrow y + 2 = 5x + 4 + 2
\]
\[
\Rightarrow y + 2 = 5x
\]
\[
\Rightarrow 5(y + 2) = 5 \cdot 5x
\]
\[ 5y + 5 \cdot 2= x \Rightarrow 5y + 4 = x= f^{-1}(y) \]
\[ \text{Man erhält } f^{-1}(x)= 5x+4. \]
Hinweis:
In \( \mathbb{Z}/m \) sei eine lineare Gleichung der Form \( ax + b = 0 \) gegeben.
Es sei \( d = \text{ggT}(m, a) \). Gilt \( \frac{b}{d} = k \) mit \( k \in \mathbb{Z} \) (das bedeutet, \( d \) teilt \( b \)), dann ist die Lösungsmenge der Gleichung nicht leer. Die Anzahl der modulo \( m \) verschiedenen Lösungen entspricht genau \( d \).
Beispiel:
\[
\text{In } \mathbb{Z} / 7 \text{ lösen wir}
\]
\[
\text{die Gleichung } 5x + 4 = 0.
\]
\[
5x + 4 = 0 \Rightarrow 5x + 4 + 3 = 0 + 3
\]
\[
\Rightarrow 5x = 3 \Rightarrow 3 \cdot 5x = 3 \cdot 3 \Rightarrow x = 2
\]
Beispiel:
\[ \text{In } \mathbb{Z} / 6 \]
\[
\text{suchen wir die zwei kleinsten positiven Zahlen, die die Gleichung } 2x = 2 \text{ erfüllen.}
\]
\[
2x = 2 \pmod{6} \Rightarrow \frac{2x}{2} = \frac{2}{2} \pmod{\frac{6}{2}}
\]
\[
\Rightarrow x \equiv 1 \pmod{3}
\]
Daraus folgt, dass die Lösung von \( 2x = 2 \) in \( \mathbb{Z} / 6 \) der Lösung von \( x = 1 \) in \( \mathbb{Z} / 3 \) entspricht.
Damit ergeben sich die Lösungen im Definitionsbereich zu:
\[
x_1 = 1 \quad \text{und} \quad x_2 = 1 + 3 = 4
\]
Beispiel:
\[ \text{In } \mathbb{Z} / 5 \]
\[
\text{wollen wir die Lösungsmenge der Gleichung } x^2 + 4x = 2 \text{ bestimmen.}
\]
\[
x^2 + 4x = 2 \Rightarrow x^2 + 4x + 3 = 2 + 3
\]
\[
\Rightarrow x^2 + 4x + 3 = 0
\]
\[
\Rightarrow (x + 1)(x + 3) = 0
\]
\[
\Rightarrow x + 1 = 0 \quad \text{oder} \quad x + 3 = 0
\]
\[
\Rightarrow x = 4 \quad \text{oder} \quad x = 2
\]
Daraus ergibt sich die Lösungsmenge:
\[
L = \{2, 4\}
\]
Beispiel:
\[
\text{In } (\mathbb{Z} / 7)^2
\]
\[
\begin{cases}
x + 2y = 1 \\
2x + 3y = 6
\end{cases}
\]
Wir wollen den Wert für \( y \) bestimmen, der dieses Gleichungssystem erfüllt.
Wir multiplizieren die erste Gleichung mit 5:
\[
x + 2y = 1 \Rightarrow 5(x + 2y) = 5 \cdot 1
\]
\[
\Rightarrow 5x + 3y = 5
\]
Nun addieren wir diese zur zweiten Gleichung:
\[
\begin{array}{rcl}
5x + 3y & = & 5 \\
+ \quad 2x + 3y & = & 6 \\
\hline
6y & = & 4
\end{array}
\]
\[
\Rightarrow 6 \cdot 6y = 6 \cdot 4
\]
\[
\Rightarrow y = 3
\]
Beispiel:
\[
\text{Wenn } 3^{27} \equiv x \pmod{5} \text{ gilt, suchen wir } x.
\]
\[
3^1 \equiv 3 \pmod{5}
\]
\[
3^2 \equiv 4 \pmod{5}
\]
\[
3^3 \equiv 2 \pmod{5}
\]
\[
3^4 \equiv 1 \pmod{5} \Rightarrow (3^4)^6 \equiv 1^6 \pmod{5}
\]
\[
\Rightarrow 3^3 \cdot 3^{24} \equiv 3^3 \cdot 1 \pmod{5}
\]
Da \( 3^3 \equiv 2 \pmod{5} \) gilt:
\[
\Rightarrow 3^{27} \equiv 2 \pmod{5}
\]
\[
\text{Somit ergibt sich } x = 2.
\]
Beispiel:
Wir wollen den Rest \( x \) bestimmen, den man erhält, wenn man \( (1997)^{28} \) durch 7 dividiert.
Dies entspricht der Kongruenz:
\[
(1997)^{28} \equiv x \pmod{7}
\]
Da \( 1997 \equiv 2 \pmod{7} \) gilt, folgt:
\[
(1997)^{28} \equiv 2^{28} \pmod{7} \Rightarrow 2^{28} \equiv x \pmod{7}
\]
Wir untersuchen die Potenzen von 2:
\[
2^1 \equiv 2 \pmod{7}
\]
\[
2^2 \equiv 4 \pmod{7}
\]
\[
2^3 \equiv 1 \pmod{7}
\]
Daraus ergibt sich:
\[
(2^3)^9 \equiv 1^9 \pmod{7}
\]
\[
2 \cdot 2^{27} \equiv 2 \cdot 1 \pmod{7}
\]
\[
2^{28} \equiv 2 \pmod{7}
\]
\[
\text{Somit ist } x = 2.
\]
AUFGABE 3
Wenn \( (1994)^{1996} \equiv x \pmod{5}\) gilt, wie groß ist \( x\)?
\[
\text{A) 0} \quad \text{B) 1} \quad \text{C) 2} \quad \text{D) 3} \quad \text{E) 4}
\]
Lösung:
\[
1994 \equiv -1 \pmod{5} \Rightarrow (1994)^{1996} \equiv (-1)^{1996} \pmod{5}
\]
\[
\Rightarrow (1994)^{1996} \equiv 1 \pmod{5}
\]
\[
\text{Folglich ist } x = 1.
\]
\(\textbf{Antwort: B} \)
AUFGABE 4
\[
\text{Wenn } (20)^{90} \equiv x \pmod{9} \text{ gilt, wie groß ist } x\text{?}
\]
\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]
Lösung:
\[
20 \equiv 2 \pmod{9} \Rightarrow (20)^{90} \equiv 2^{90} \pmod{9}
\]
\[
2^1 \equiv 2 \pmod{9}
\]
\[
2^2 \equiv 4 \pmod{9}
\]
\[
2^3 \equiv -1 \pmod{9}
\]
\[
(2^3)^{30} \equiv (-1)^{30} \pmod{9}
\]
\[
2^{90} \equiv 1 \pmod{9}
\]
\[
\text{Folglich ist } x = 1.
\]
\(\textbf{Antwort: B} \)
AUFGABE 5
\[
\text{Wie groß ist der Rest bei der Division des Produkts } 6^{25} \cdot 7^{13} \text{ durch 5?}
\]
\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]
Lösung:
\[
\text{Wir suchen } x \text{ in der Beziehung } 6^{25} \cdot 7^{13} \equiv x \pmod{5}.
\]
\[
6 \equiv 1 \pmod{5} \Rightarrow 6^{25} \equiv 1^{25} \pmod{5}
\]
\[
\Rightarrow 6^{25} \equiv 1 \pmod{5}
\]
\[
7 \equiv 2 \pmod{5} \Rightarrow 7^4 \equiv 2^4 \equiv 1 \pmod{5}
\]
\[
\Rightarrow (7^4)^3 \equiv 1^3 \pmod{5}
\]
\[
\Rightarrow 7 \cdot 7^{12} \equiv 7 \cdot 1 \pmod{5}
\]
\[
\Rightarrow 7^{13} \equiv 2 \pmod{5}
\]
\[
\text{Da } 6^{25} \equiv 1 \pmod{5} \text{ und } 7^{13} \equiv 2 \pmod{5} \text{ gelten, folgt:}
\]
\[
6^{25} \cdot 7^{13} \equiv 1 \cdot 2 \pmod{5}
\]
\[
\Rightarrow x = 2
\]
\(\textbf{Antwort: C} \)
Hinweis: (Der kleine Fermatsche Satz)
Wenn \( x \) und \( m \) teilerfremd sind und \( m \) eine Primzahl ist, gilt:
\[
x^{m-1} \equiv 1 \pmod{m}
\]
Es ist jedoch möglich, dass man den Wert 1 bereits bei einer kleineren Potenz als \( m – 1 \) erhält.
Beispiele:
\[
2^{10} \equiv 1 \pmod{11}
\]
\[
6^{22} \equiv 1 \pmod{23}
\]
AUFGABE 6
\[
\text{Wenn } 7^{61} \equiv x \pmod{11} \text{ gilt, wie groß ist } x\text{?}
\]
\[
\text{A) } 4 \quad \text{B) } 5 \quad \text{C) } 6 \quad \text{D) } 7 \quad \text{E) } 8
\]
Lösung:
\[
\text{Da } m = 11 \text{ eine Primzahl ist, gilt } m – 1 = 10\text{. Nach dem kleinen Fermatschen Satz folgt:}
\]
\[
7^{10} \equiv 1 \pmod{11}
\]
\[
(7^{10})^6 \equiv 1^6 \pmod{11}
\]
\[
7^{60} \equiv 1 \pmod{11}
\]
\[
7 \cdot 7^{60} \equiv 7 \cdot 1 \pmod{11}
\]
\[
7^{61} \equiv 7 \pmod{11} \implies x = 7
\]
\(\textbf{Antwort: D} \)
AUFGABE 7
\[
\text{Wenn } 5^{120} \equiv x \pmod{13} \text{ gilt, wie groß ist } x\text{?}
\]
\[
\text{A) } 1 \quad \text{B) } 5 \quad \text{C) } 7 \quad \text{D) } 9 \quad \text{E) } 11
\]
Lösung:
\[
\text{Da } m = 13 \text{ eine Primzahl ist, gilt } m – 1 = 12\text{. Nach dem kleinen Fermatschen Satz folgt:}
\]
\[
5^{12} \equiv 1 \pmod{13}
\]
\[
(5^{12})^{10} \equiv 1^{10} \pmod{13}
\]
\[
5^{120} \equiv 1 \pmod{13} \implies x = 1
\]
\(\textbf{Antwort: A} \)
Hinweis:
In der Kongruenz \( x^n \equiv y \pmod{m} \) kann auf der rechten Seite niemals der Wert 1 entstehen, wenn \( x \) und \( m \) nicht teilerfremd sind. Stattdessen erhält man auf der rechten Seite die Zahl 0 oder eine sich wiederholende Zahlenfolge.
Beispiel:
\[
(18)^{100} \equiv 0 \pmod{64}
\]
AUFGABE 8
\[
\text{Wie groß ist der Rest bei der Division von } 2^{100} \text{ durch 6?}
\]
\[
\text{A) } 1 \quad \text{B) } 2 \quad \text{C) } 3 \quad \text{D) } 4 \quad \text{E) } 5
\]
Lösung:
\[
\text{Wir bestimmen } x \text{ in der Gleichung } 2^{100} \equiv x \pmod{6}.
\]
Wir untersuchen die fortlaufenden Potenzen von 2 modulo 6:
\[
2^1 \equiv 2 \pmod{6}
\]
\[
2^2 \equiv 4 \pmod{6}
\]
\[
2^3 \equiv 2 \pmod{6}
\]
\[
2^4 \equiv 4 \pmod{6}
\]
\[
\vdots
\]
Es zeigt sich ein periodisches Muster, bei dem ungerade Potenzen kongruent zu 2 und gerade Potenzen kongruent zu 4 sind:
\[
2^{99} \equiv 2 \pmod{6}
\]
\[
2^{100} \equiv 4 \pmod{6} \implies x = 4
\]
\(\textbf{Antwort: D} \)
Hinweis: (Der Satz von Euler)
In der Beziehung \( x^n \equiv y \pmod{m} \) seien \( x \) und \( m \) teilerfremd. Die Primfaktorzerlegung von \( m \) laute:
\[
m = a^p \cdot b^r \cdot c^s \cdots
\]
Für die Eulersche Phi-Funktion \( \phi(m) \) (hier als \( z \) bezeichnet) gilt:
\[
z = \phi(m) = m \cdot \left( 1 – \frac{1}{a} \right) \cdot \left( 1 – \frac{1}{b} \right) \cdot \left( 1 – \frac{1}{c} \right) \cdots
\]
Unter diesen Bedingungen gilt stets:
\[
x^z \equiv 1 \pmod{m}
\]
AUFGABE 9
Welche Ziffer steht an der Einerstelle der Zahl \( (1997)^{62} \)?
\[
\text{A) } 5 \quad \text{B) } 6 \quad \text{C) } 7 \quad \text{D) } 8 \quad \text{E) } 9
\]
Lösung:
Die Einerstelle einer Zahl entspricht genau dem Rest, den man erhält, wenn man diese Zahl durch 10 dividiert.
\[
\text{Wir berechnen somit } x \text{ für die Kongruenz } (1997)^{62} \equiv x \pmod{10}.
\]
Da \( 1997 \equiv 7 \pmod{10} \) ist, gilt:
\[
(1997)^{62} \equiv 7^{62} \pmod{10} \Rightarrow 7^{62} \equiv x \pmod{10}
\]
Wir bestimmen den Wert der Eulerschen Phi-Funktion für \( m = 10 = 2 \cdot 5 \):
\[
z = \phi(10) = 10 \cdot \left( 1 – \frac{1}{2} \right) \cdot \left( 1 – \frac{1}{5} \right) = 4
\]
Nach dem Satz von Euler gilt:
\[
7^4 \equiv 1 \pmod{10}
\]
\[
(7^4)^{15} \equiv 1^{15} \pmod{10} \implies 7^{60} \equiv 1 \pmod{10}
\]
Wir multiplizieren beide Seiten mit \( 7^2 \):
\[
7^2 \cdot 7^{60} \equiv 7^2 \cdot 1 \pmod{10}
\]
Da \( 7^2 = 49 \equiv 9 \pmod{10} \) gilt, folgt:
\[
\Rightarrow 7^{62} \equiv 9 \pmod{10}
\]
Daraus ergibt sich \( x = 9 \).
\(\textbf{Antwort: E} \)
AUFGABE 10
\[
\text{Welche Zahl bilden die letzten beiden Ziffern von } (21)^{202}\text{?}
\]
\[
\text{A) } 01 \quad \text{B) } 21 \quad \text{C) } 41 \quad \text{D) } 61 \quad \text{E) } 81
\]
Lösung:
\[
\text{Gesucht ist } x \text{ in der Kongruenz } (21)^{202} \equiv x \pmod{100}.
\]
Wir betrachten den Modul \( m = 100 = 2^2 \cdot 5^2 \).
\[
\Rightarrow z = \phi(100) = 100 \cdot \left( 1 – \frac{1}{2} \right) \cdot \left( 1 – \frac{1}{5} \right) = 40
\]
Nach dem Satz von Euler gilt:
\[
(21)^{40} \equiv 1 \pmod{100}
\]
\[
((21)^{40})^5 \equiv 1^5 \pmod{100} \implies (21)^{200} \equiv 1 \pmod{100}
\]
Wir multiplizieren mit \( (21)^2 \):
\[
(21)^2 \cdot (21)^{200} \equiv (21)^2 \cdot 1 \pmod{100}
\]
\[
(21)^{202} \equiv 441 \pmod{100}
\]
Da \( 441 \equiv 41 \pmod{100} \) gilt, folgt:
\[
(21)^{202} \equiv 41 \pmod{100} \implies x = 41
\]
\(\textbf{Antwort: C} \)
AUFGABE 11
\[
\text{Wenn } 3^{27} + 4^{27} + 6^{27} + (12)^{27} \equiv x \pmod{5} \text{ gilt, wie groß ist } x\text{?}
\]
\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]
Lösung:
Wir reduzieren die Basen modulo 5:
\[
3 \equiv -2 \pmod{5}, \quad 6 \equiv 1 \pmod{5}
\]
\[
4 \equiv -1 \pmod{5}, \quad 12 \equiv 2 \pmod{5}
\]
Setzen wir diese Werte in den Ausdruck ein:
\[
3^{27} + 4^{27} + 6^{27} + (12)^{27} \equiv x \pmod{5}
\]
\[
\Rightarrow (-2)^{27} + (-1)^{27} + 1^{27} + 2^{27} \equiv x \pmod{5}
\]
Da \( (-2)^{27} = -(2^{27}) \) und \( (-1)^{27} = -1 \) gelten, heben sich die symmetrischen Terme paarweise auf:
\[
\Rightarrow 0 \equiv x \pmod{5} \implies x = 0
\]
\(\textbf{Antwort: A} \)
← Vorherige Seite | Nächste Seite →