Satz. Sind \(n,m \in \mathbb{Z}\), dann gibt es \(\alpha,\beta\in \mathbb{Z}\), so dass
\(\operatorname{ggT}(n,m) = \alpha n + \beta m\)
ist.
Die Koeffizienten \(\alpha\) und \(\beta\) können mit dem erweiterten euklidischen Algorithmus bestimmt werden.
Sei p =12619 (das ist eine Primzahl) und [x]= [810]p
Laut obigem Satz gibt es \(\alpha,\beta\in \mathbb{Z}\), so dass
\(\operatorname{ggT}(12619,810) = \alpha\cdot 12619 + \beta\cdot 810\)
ist.
Weil \(12619\) eine Primzahl ist, ist \(\operatorname{ggT}(12619,810) = 1\). Also gibt es \(\alpha,\beta\in \mathbb{Z}\), so dass
\(1 = \alpha\cdot 12619 + \beta\cdot 810\)
ist. Für diese \(\alpha,\beta\) ist wegen
\(\alpha\cdot 12619 \equiv 0 \mod 12619\)
auch
\(\beta\cdot 810\equiv 1 \mod 12619\)
und somit
\([810]_{12619}^{-1} = [\beta]_{12619}\).
