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}