\section{Mathe}

\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
\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}
\lstinputlisting{math/multInv.cpp}

\subsubsection{Faktorisierung}
\lstinputlisting{math/factor.cpp}

\subsubsection{Mod-Exponent über $\mathbb{F}_p$}
\lstinputlisting{math/modExp.cpp}

\subsection{LGS über $\mathbb{F}_p$}
\lstinputlisting{math/lgsFp.cpp}

\subsection{Binomialkoeffizienten}
\lstinputlisting{math/binomial.cpp}

\subsection{Primzahlsieb von Eratosthenes}
\lstinputlisting{math/primeSieve.cpp}

\subsection{Satz von \textsc{Sprague-Grundy}}
Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
\[
	g\left(X\right) := \min\{ \mathbb{Z}_0^+ \textbackslash \{g\left(Y\right)~|~Y \text{ von } X \text{ aus direkt erreichbar}\}\} 
\]
$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\
Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.