uni/sose2020/proseminar/skript.tex

\documentclass{../../lecture}

\begin{document}

\setcounter{section}{3}

\section{Prime Restklassen und der Satz von Euler-Fermat}

\textit{
    Einleitung
    \begin{itemize}
        \item Eigenschaften von $\Z / n \Z$
        \item Lösung von Kongruenzen
        \item Satz von Euler-Fermat
    \end{itemize}
}

\begin{definition}[Nullteiler]
    Es sei $R$ ein Ring. Ein Element $x \in R$ heißt ein Nullteiler, wenn es ein $y \in R, y\neq 0$
    mit $xy = 0$ gibt. Der Ring $R$  heißt nullteilerfrei, wenn $R \neq 0$  ist und
    0 der einzige Nullteiler in $R$ ist.
\end{definition}

\textit{Anmerkung: Der Nullring ist nicht nullteilerfrei und die 0 ist kein Nullteiler, da kein
$y \in R, y \neq 0$ existiert.}

\begin{bsp}
    \begin{itemize}
        \item Nullring hat keinen Nullteiler, da kein $y \in R$, $y \neq 0$ existiert.
        \item Nullteiler in $\Z / 3\Z: \overline{0}$, also ist $\Z / 3 \Z$ nullteilerfrei.
        \item Nullteiler in $\Z / 4 \Z: \overline{0}$, $\overline{2}$ ($\overline{2}\cdot \overline{2} = \overline{4} = \overline{0}$), also nicht nullteilerfrei.
    \end{itemize}
\end{bsp}

\begin{definition}[Einheit]
    Es sei $R$ ein Ring. Ein Element $x \in R$  heißt eine Einheit, wenn es ein $y \in R$ mit $xy = 1$ gibt.
    Bezeichnung: $x^{-1} := y$.
    Die Einheiten im Ring $\Z/n\Z$ heißen \underline{prime Restklassen modulo n}.
    \textit{also: wenn ein Inverses bezüglich Multiplikation existiert}
\end{definition}

\begin{bsp}
    \begin{itemize}
        \item Einheiten in $\Z / 3\Z: \overline{1}$, $\overline{2}$
            ($\overline{2} \cdot \overline{2} = \overline{4} = \overline{1}$).
        \item Einheiten in $\Z / 4\Z: \overline{1}, \overline{3}$:
            ($\overline{3} \cdot \overline{3} = \overline{9} = \overline{1}$)
    \end{itemize}
\end{bsp}

\begin{lemma}
    \label{lemma:einheitengruppe}
    Es sei $R$ ein Ring. Dann gilt
    \begin{enumerate}[(a)]
        \item $R^{\times } := \{ x \in R  \mid x \text{ ist eine Einheit}\} $ ist eine abelsche
            Gruppe bezüglich der Multiplikation, die sogenannte Einheitengruppe von $R$.
            Insbesondere gibt es für jedes $x \in R^{\times }$ genau ein $y \in R^{\times }$ mit
            $xy = 1$. Dieses Element bezeichnen wir mit $x^{-1}$ und nennen es das
            (multiplikativ) Inverse zu $x$.

            Die Gruppe $(\Z / n \Z)^{\times}$ wird als \underline{prime Restklassengruppe modulo n} bezeichnet.
        \item Ist $x \in R^{\times }$, dann ist $x$ kein Nullteiler.
            \label{lemma:einheitengruppe:nullteiler}
        \item Falls $R$ endlich ist, dann gilt auch die Umkehrung von (b): Ist $x \in R$ kein Nullteiler,
            dann ist $x$ eine Einheit.
    \end{enumerate}
    \textit{Insbesondere gilt im Fall $R = \Z / n \Z$ , $n \in \N$, für $\overline{x} \in R$, dass $\overline{x}$
    genau dann eine Einheit ist, wenn $\overline{x}$ kein Nullteiler ist.}
\end{lemma}

\begin{proof}
    \begin{enumerate}[(a)]
        \item Sind $a, b \in R^{\times }$, dann ist auch $ab \in R^{\times }$, denn dann existieren
            $c, d \in R$ mit $ac = 1$, $bd = 1$, damit folgt
            $(ab)(cd) = (ac)(bd) = 1$.

            Assoziativität und Kommutativität folgen aus der Multiplikation in $R$.

            Neutrales Element: $1 \in R^{\times}$ wegen $1 \cdot 1 = 1$.

            Inverse: Ist $a \in R^{\times}$, dann existiert nach Definition ein $b \in R$ mit
            $ab = 1 \implies ba = 1$. Damit folgt $b \in R^{\times }$.

            Damit ist $R^{\times }$ eine abelsche Gruppe bezüglich der Multiplikation.
        \item Falls $R = 0$, dann ist $0 = 1$ also eine Einheit, aber kein Nullteiler. Falls
            $R \neq 0$: Sei $x \in R^{\times }$ und $y \in R$ mit $xy = 0$. Damit folgt
            $y = x^{-1}xy = x^{-1} \cdot 0 = 0$, also ist $x$ kein Nullteiler.
        \item Sei $R$ endlich und $x \in R$ kein Nullteiler. Wir betrachten die Abbildung
            $\tau: R \to R, a \mapsto xa$. $\tau$ ist injektiv, denn aus $\tau(a) = \tau(b)$
            folgt $xa = xb \implies x(a-b) = 0$. Da $x$ kein Nullteiler ist, folgt damit
            $a - b = 0 \implies a = b$. Als injektive Selbstabbildung der endlichen Menge $R$ ist
            $\tau$ auch surjektiv, damit existiert ein $y \in R$ mit $\tau(y) = 1$, was
            $xy = 1$ und deshalb $x \in R^{\times}$ impliziert.
    \end{enumerate}
\end{proof}

\begin{definition}[Körper]
    Ein Ring $R$ heißt ein Körper, wenn $R^{\times } = R \setminus \{0\}$ ist.
\end{definition}

\textit{Anmerkung: Nullring $R = 0$ ist nach Definition kein Körper}

\begin{bsp}
    $\Z / 3\Z$ ist ein Körper, $\Z / 4 \Z$ ist kein Körper.
\end{bsp}

\begin{satz}
    Es sei $n \in \N$. Dann sind äquivalent
    \begin{enumerate}[(i)]
        \item $n$ ist eine Primzahl
        \item $\Z / n \Z$ ist ein Körper
        \item $\Z / n \Z$ ist nullteilerfrei.
    \end{enumerate}
    Für Primzahlen $p$ schreiben wir auch $\mathbb{F}_p := \Z / p \Z$.
\end{satz}

\begin{proof}
    (i) $\implies$ (ii): Sei $n$ eine Primzahl, $\overline{a} \in \Z / n \Z$, $\overline{a} \neq 0$.
    Zz.: $a \in (\Z / n \Z)^{\times}$. Wegen $\overline{a} \neq 0$ folgt $n \nmid a$. Da
    $n$ eine Primzahl ist, erhalten wir $\text{ggT}(n,a) = 1$. Aufgrund des erweiterten
    Euklidischen Algorithmus gibt es $u, v \in \Z$ mit
    $un + va = 1 \implies \overline{un} + \overline{va} = \overline{1} \implies \overline{v} \cdot \overline{a} = \overline{1}$.
    Mit $\overline{a}^{-1} := \overline{v}$ folgt $a \in R^{\times}$.

    (ii) $\implies$ (iii): Sei $\Z / n \Z$ ein Körper. Damit ist $\Z / n \Z \neq 0$ und
    $(\Z / n \Z)^{\times} = \Z / n \Z \setminus \{0\}$. Wegen \ref{lemma:einheitengruppe}
    \ref{lemma:einheitengruppe:nullteiler} ist dann $\overline{0}$ der einzige
    Nullteiler in $\Z / n \Z$, d.h. $\Z / n \Z$ ist nullteilerfrei.

    (iii) $\implies$ (i): Kontraposition: Sei $n$ keine Primzahl. Falls $n = 1$, dann ist
    $\Z / n \Z = 0$, also nicht nullteilerfrei. Falls $n > 1$ ist, dann gibt es $a, b \in \N$
    mit $1 < a,b < n$, so dass $n = ab$ gilt. Damit folgt
    $\overline{0} = \overline{n} = \overline{ab} = \overline{a} \overline{b}$ mit
    $\overline{a}, \overline{b} \neq 0$, also sind $\overline{a}$, $\overline{b}$ Nullteiler,
    insbesondere ist $\Z / n \Z$ nicht nullteilerfrei.
\end{proof}

\textit{Anmerkung: Letzte Woche haben wir bereits Kongruenzrelationen in $\Z$ kennengelernt, heute:
lernen Kongruenzen zu lösen. Frage: Wann hat eine Kongruenz eine Lösung in $\Z$?}
\vspace{5mm}

\begin{lemma}
    Es seien $a$, $b \in \Z$, $n \in \N$. Dann sind äquivalent:
    \begin{enumerate}[(i)]
        \item Die Kongruenz $ax \equiv b$ $(\text{mod } n)$ besitzt eine Lösung in $\Z$.
        \item $\text{ggT}(a,n) \mid b$.
    \end{enumerate}
    \label{lemma:kongruenz}
\end{lemma}

\begin{proof}
    (i) $\implies$ (ii): Sei $x \in \Z$ mit $ax \equiv b$ $(\text{mod }n)$. Dann gilt
    $n \mid (ax - b) \implies \exists k \in \Z$ mit $ax - b = kn$, also mit $b = ax - kn$. Wegen
    $\text{ggT}(a,n) \mid a$ und $\text{ggT}(a,n) \mid n$ folgt $\text{ggT}(a,n) \mid b$.

    (ii) $\implies$ (i): Es gelte $\text{ggT}(a,n)  \mid b$. Aus dem erweiterten Euklidischen Algorithmus
    folgt die Existenz von $u$, $v \in \Z$ mit
    \[
        ua + vn = \text{ggT}(a,n)
    .\] Durch Multiplikation mit der nach Voraussetzung ganzen Zahl $\frac{b}{\text{ggT}(a,n)}$ erhalten
    wir
    \[
        ua \frac{b}{\text{ggT}(a,n)} + vn \frac{b}{\text{ggT}(a,n)} = b
    ,\] was die Kongruenz
    \[
        a \cdot \frac{bu}{\text{ggT}(a,n)} \equiv b \quad (\text{mod }n)
    \] und damit die Behauptung zeigt.
\end{proof}

\begin{bsp}
    %\begin{enumerate}[(a)]
        %\item Die Kongruenz $15x \equiv 7$ $(\text{mod } 21)$ hat wegen $ggT(15,21) = 3 \nmid 7$ keine
        %    Lösung.
        %\item
    Die Kongruenz $15x \equiv 6$ $(\text{mod } 21)$ hat wegen $\text{ggT}(15,21) = 3  \mid 6$ eine Lösung.
    Der erweiterte Euklidische Algorithmus ergibt
    \[
        \text{ggT}(15, 21) = 3 = 3 \cdot 15 + (-2) \cdot 21
    .\] Damit folgt \textit{wie im Beweis durch Multiplikation mit 2}
    \[
        6 = 6 \cdot 15 + (-4) \cdot 21 \equiv 15 \cdot 6 \quad (\text{mod } 21)
    \] d.h. $x = 6$ ist eine Lösung der Kongruenz.
    %\end{enumerate}
\end{bsp}

\begin{korrolar}
    Es sei $a \in \Z, n \in \N$. Dann sind äquivalent
    \begin{enumerate}[(i)]
        \item Die Kongruenz $ax \equiv 1$ $(\text{mod } n)$ besitzt eine Lösung in $\Z$.
        \item $\overline{a} \in (\Z / n\Z)^{\times }$
        \item $\text{ggT}(a,n) = 1$
    \end{enumerate}
\end{korrolar}

\begin{proof}
    (i) $\iff$ (ii): Die Kongruenz $ax \equiv 1$ $(\text{mod }n)$ entspricht der Gleichung
    $\overline{a} \cdot \overline{x} = \overline{1}$ in $\Z / n \Z$, welche
    genau dann lösbar ist, wenn $\overline{x}$ eine Einheit in $\Z / n \Z$ ist.

    (i) $\iff$ (iii): $\text{ggT}(a,n) = 1 \iff \text{ggT}(a,n) \mid 1$.
    \textit{Anmerkung: Hinrichtung klar, Rückrichtung: $\text{ggT}(a,n)  \mid 1$ heißt,
    1 ist ein Vielfaches des $\text{ggT}(a,n)$, d.h.
    der $\text{ggT}(a,n)$ ist bereits 1}. Folgt mit $b = 1$ aus
    \ref{lemma:kongruenz}.

    \textit{Hier wird klar, warum die Einheiten in $\Z / n \Z$ prime Restklassen heißen:
    teilerfremd wird auch als relativ prim bezeichnet.}
\end{proof}

\textit{Frage: Wie können große Potenzen modulo n vereinfacht werden? Dazu wird Satz v. Euler-Fermat
helfen, dafür brauchen wir aber noch ein paar Definitionen}

\begin{definition}[Ordnung]
    Es sei $G$ eine endliche Gruppe. Die Ordnung von $G$ (Notation: $|G|$) ist definiert als die Anzahl
    der Elemente von $G$.
\end{definition}

\begin{definition}[Eulersche $\varphi$-Funktion]
    Die Abbildung
    \begin{align*}
        \varphi \colon &\N \to \N \\
                       &n \mapsto |(\Z / n \Z)^{\times}| = \# \{ a \in \N_0  \mid 0 \le a < n \text{ und } \text{ggT}(a,n) = 1\} 
    .\end{align*}
\end{definition}

\textit{Anmerkung: also zählt die $\varphi$-Funktion die zu einer Zahl $n$ teilerfremden Zahlen zwischen
$0$ und $n$.}

\begin{bsp}
    \begin{enumerate}[(a)]
        \item Es ist wie $(\Z / 4 \Z)^{\times} = \{\overline{1}, \overline{3}\} $, also $\varphi(4) = 2$.
        \item Sei $p$ eine Primzahl. Dann ist $\Z / p \Z$ ein Körper, d.h.
            \[
                \varphi(p) = |(\Z / p\Z)^{\times }| = \# \{\Z / p \Z\} - 1 = p - 1
            .\] 
    \end{enumerate}
\end{bsp}

\begin{lemma}
    Es sei $p$ eine Primzahl und $n \in \N$. Dann gilt
    \[
        \varphi(p^{n}) = p^{n-1}(p-1)
    .\] 
\end{lemma}

\begin{proof}
    $\exists $ genau $p^{n-1}$ Zahlen $a$ mit $0 \le a < p^{n}$ und $\text{ggT}(a,n) > 1$, denn:
    Primfaktorzerlegung von $p^{n} = \underbrace{p \cdot p \cdot \ldots \cdot p}_{n-\text{mal}}$
    $\implies$ Zahlen $a$ sind die $p^{n-1}$ Vielfachen von $p$, also
    $0 \cdot p, 1\cdot p, \ldots, (p^{n-1} - 1)\cdot p \implies \varphi(p^{n})=p^{n} - p^{n-1} = p^{n-1}(p-1)$.
\end{proof}

Notation für Gruppen: Verknüpfung multiplikativ und neutrales Element ist $1$.

\begin{lemma}
    \label{lemma:endlichegruppe}
    Es sei $G$ eine endliche abelsche Gruppe und $g \in G$. Dann gilt
    \[
    g^{|G|} = 1
    .\] 
\end{lemma}

\begin{proof}
    Betrachte die Abbildung $\tau_g\colon G \to  G, x \mapsto gx$. Diese ist injektiv, denn
    aus $\tau_g(x) = \tau_g(y)$ für $x, y \in G$ folgt $gx = gy$ und nach Linkskürzung $x = y$. Als injektive
    Selbstabbildung auf der endlichen Gruppe $G$, ist $\tau_g$ auch surjektiv, also bijektiv.
    Da $G$ endlich folgt damit
    \[
    \prod_{x \in G} x \qquad \qquad\stackrel{\tau \text{ bijektiv, } G \text{ abelsch}}{=} \qquad\qquad \prod_{x \in G} \tau_g(x) = \prod_{x \in G} gx = g^{|G|} \prod_{x \in G} x
    .\] Mit Rechtskürzung folgt damit $g^{|G|} = 1$.
\end{proof}

\begin{satz}[Satz von Euler-Fermat]
    Es sei $n \in \N$ und $\overline{a} \in (\Z / n \Z)^{\times }$. Dann gilt
    \[
        \overline{a}^{\varphi(n)} = \overline{1}
    .\] 
\end{satz}

\begin{proof}
    Nach Definition ist $\varphi(n) = |(\Z / n \Z)^{\times }|$. Die Behauptung folgt damit direkt aus
    \ref{lemma:endlichegruppe} mit $G = (\Z / n \Z)^{\times }$.
\end{proof}

\begin{bsp}
    \begin{enumerate}[(1)]
        \item Es ist $3^{19} \equiv 10$ $(\text{mod } 17)$, denn $\overline{3} \in (\Z / 17 \Z)^{\times}$ und
            \[
                3^{16} = 3^{\varphi(17)} \qquad\qquad \stackrel{\text{Satz v. Euler-Fermat}}{\equiv} \qquad \qquad 1 \quad (\text{mod } 17)
            .\] Damit folgt
            \[
                3^{19} = 3^{3} \cdot 3^{16} \equiv 27 \cdot 1 \equiv 10 \quad (\text{mod } 17)
            .\] 
        \item Was ist die letzte Dezimalstelle von $7^{222}$? Also welche Zahl ist
            $7^{222}$ kongruent modulo 10?

            Zunächst $\varphi(10) = 4$. Und $\text{ggT}(7,10) = 1$. Dann folgt
            \[
                7^{4} = 7^{\varphi(10)} \qquad\qquad \stackrel{\text{Satz v. Euler-Fermat}}{\equiv}
                \qquad \qquad 1 \quad (\text{mod } 10)
            .\] Dann teile $222$ durch $4$ mit Rest. Damit
            \[
                7^{222} = 7^{4 \cdot 55 + 2} = (7^{4})^{55}  \cdot 7^{2} \equiv 1^{55} \cdot 7^{2}
                \equiv 49 \equiv 9 \quad (\text{mod } 10)
            .\] 
    \end{enumerate}
\end{bsp}

\begin{korrolar}[Kleiner Satz von Fermat]
    Es sei $p$ eine Primzahl. Dann gilt
    \begin{enumerate}[(a)]
        \item Für jedes $\overline{a} \in \mathbb{F}_p^{\times }$ ist $\overline{a}^{p-1} = \overline{1}$.
        \item Für jedes $\overline{a} \in \mathbb{F}_p$ ist $\overline{a}^{p} = \overline{a}$.
    \end{enumerate}
\end{korrolar}

\begin{proof}
    \begin{enumerate}[(a)]
        \item Mit $\varphi(p) = p - 1$ folgt das direkt aus dem Satz von Euler-Fermat.
        \item Falls $\overline{a} \in \mathbb{F}_p^{\times }$: Dann ist
            $\overline{a}^{p} = \overline{a} \cdot \overline{a}^{p-1} = \overline{a} \cdot \overline{1} = \overline{a}$.
            Falls $\overline{a} = \overline{0}$ ist $\overline{a}^{p} = \overline{0}^{p} = \overline{0} = \overline{a}$.
    \end{enumerate}
\end{proof}

\end{document}