modulares Inverses

1 files changed, 12 insertions, 0 deletions

diff --git a/math/math.tex b/math/math.tex
index 0b66163..f82ab65 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -4,5 +4,17 @@
 \lstinputlisting{math/gcd-lcm.cpp}
 \lstinputlisting{math/extendedEuclid.cpp}
 
+\subsubsection{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
+Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
+\begin{description}
+	\item[Falls $d = 1$:] ~
+	\begin{itemize}[nosep]
+		\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit $\alpha x + \beta n = 1$
+		\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$
+		\item $x^{-1} :\equiv \alpha \mod n$
+	\end{itemize}
+	\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
+\end{description}
+
 \subsection{Binomialkoeffizienten}
 \lstinputlisting{math/binomial.cpp}
\ No newline at end of file