blob: 5dea881942c144cbea476d241d1d30596c2eb363 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
Die Zahl $p=47$ ist eine Primzahl, der Ring
$\mathbb{Z}/p\mathbb{Z}=\mathbb{F}_{47}$ ist daher ein Körper.
Jeder von Null verschiedene Rest $b\in\mathbb{F}_p^*$ hat daher eine
multiplikative Inverse.
Berechnen Sie die multiplikative Inverse von $b=11\in\mathbb{F}_{47}$.
\begin{loesung}
Der euklidische Algorithmus muss auf die Zahlen $p=47$ und $b=11$ angewendet
werden, es ergeben sich die Quotienten und Reste der folgenden Tabelle:
\begin{center}
\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
\hline
k&a_k&b_k&q_k&r_k\\
\hline
0& 47& 11& 4& 3\\
1& 11& 3& 3& 2\\
2& 3& 2& 1& 1\\
3& 2& 1& 2& 0\\
\hline
\end{tabular}
\end{center}
Wie erwartet ist der grösste gemeinsame Teiler
$\operatorname{ggT}(47,11)=r_2=1$.
Um die Zahlen $s,t$ zu finden, für die $sp+tb=1$ gilt, können wir die
Matrixform verwenden, wir berechnen dazu
\begin{align*}
Q
=
Q(2)Q(1)Q(3)Q(4)
&=
\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
\begin{pmatrix} 0&1\\1&-1 \end{pmatrix}
\begin{pmatrix} 0&1\\1&-3 \end{pmatrix}
\begin{pmatrix} 0&1\\1&-4 \end{pmatrix}
\\
&=
\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
\begin{pmatrix} 0&1\\1&-1 \end{pmatrix}
\begin{pmatrix} 1&-4\\-3&13\end{pmatrix}
\\
&=
\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
\begin{pmatrix} -3&13\\4&-17 \end{pmatrix}
\\
&=
\begin{pmatrix} 4&-17\\ -11&47 \end{pmatrix}.
\end{align*}
Daraus kann man ablesen, dass $s=4$ und $t=-17$, tatsächlich ist
$4\cdot 47-17\cdot 11=188-187=1$.
Wir schliessen daraus, dass $-17=30\in\mathbb{F}_{47}$ die multiplikative
Inverse von $b=11$ ist.
Die Rechnung $11\cdot 30 = 330 = 7\cdot 47 + 1$ zeigt, dass dies
der Fall ist.
Alternativ zur Matrixdarstellung kann man die Koeffizienten $s$ und $t$
auch mit Hilfe der erweiterten Tabelle finden:
\begin{center}
\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
\hline
k&a_k&b_k&q_k&r_k&c_k&d_k\\
\hline
& & & & & 1& 0\\
0& 47& 11& 4& 3& 0& 1\\
1& 11& 3& 3& 2& 1& -4\\
2& 3& 2& 1& 1& -3& 13\\
3& 2& 1& 2& 0& {\color{red}4}&{\color{red}-17}\\
4& 1& 0& & &-11& 47\\
\hline
\end{tabular}
\end{center}
Die gesuchten Zahlen $s$ und $t$ sind rot hervorgehoben.
\end{loesung}
|
