diff options
Diffstat (limited to 'math/math.tex')
| -rw-r--r-- | math/math.tex | 12 |
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 |