Kongruenzen

Die Kongruenz-Relation \(\equiv_m\) setzt ganze Zahlen, die den gleichen rest bei der Division durch eine natürliche Zahl \(n\ge 1\) haben, in Relation.

Definition 9: Kongruenz

Sei \(m,a,b \in \mathbb{Z}, m\ge 1\).

\(a\equiv_m b \Leftrightarrow a\equiv b (mod\;m)\Leftrightarrow a\; mod\; m= b\; mod\; m\)

Beispiel:

\(1\equiv 4\equiv 7\equiv -2 \equiv -5 \;(mod\; 3)\) //\((-5+2*3=1)\)

Äquivalenzklassen und -relationen

Da die Kongruenz mittels Gleichheit definiert ist, handelst es sich um eine Äquivalenzrelation (R, S, T). Daher gibt es sogenannte Äquivalenzklassen. Eine Äquivalenzklasse ist eine Menge, die alle Zahlen enthält, die modulo eines bestimmten Modulos einen bestimmten Rest ergeben.

Beispiel:

\([2]_5 = \{...,-8,-3,2,7,12,...\}=\{5*t+2\mid t\in \mathbb{Z}\}\)

\([r]_m = \{k*m+r\mid k\in \mathbb{Z}\}\)

Rechenregeln für Kongruenzen

• \(a \equiv_m 0 \Leftrightarrow m\mid a\)

Theorem 5:

Sei \(a,b \in \mathbb{Z}\), dann gilt für \(m\ge 1\): \(a\equiv_m b \Leftrightarrow m\mid(a-b)\)

Zu tun

Beweis

Beispiel:

\(a=22\), \(b=7\)

\(7\equiv_m 22\)

\(a-b=22-7=15 \Rightarrow 5\mid 15\)

Folgerung 8:

\(a\equiv_m b \Leftrightarrow a-b \equiv_m 0\)

Lemma 3:

Sei \(a\equiv_m b\) und \(c\equiv_m d\), dann gilt:

1. \(a+c \equiv_m b+d\)
2. \(a-c \equiv_m b-d\)
3. \(a*c \equiv_m b*d\)

Hinweis: Dies gilt insbesondere auch wenn \(c=d\). D.h. ähnlich wie bei Gleichungen können beide Seiten der Kongruenz gleichmäßig erhöht, verringert oder multipliziert werden. Vorsicht: für die Division gilt dies nicht!

Weiterhin gelten obige Regeln auch für z.B. \(c=m\) und \(d=0\). D.h. der Modul kann zu einer Seite der Kongruenz addiert, subtrahiert oder multipliziert werden, ohne die andere Seite zu verändern.

Zu tun

Beweis

Beispiel:

1. \begin{align*} 69+53 &= 122 \equiv 3 \; (mod\, 7)\\ 69+53 &\equiv 6+4 = 10 \equiv 3\; (mod\, 7) \end{align*}
2. \begin{align*} 69*53 &= 3657 \equiv 3 \; (mod\, 7)\\ 69*53 &\equiv 6*4 = 24 \equiv 3\; (mod\, 7) \end{align*}

2. \begin{align*} 69*53+29*23 &= 4324 \equiv 5 \; (mod\, 7)\\ &\equiv 6*4+1*2 \equiv 3+2 \equiv 5\; (mod\, 7) \end{align*}

Folgerung 9:

Ist \(a\equiv_m b\), dann ist auch \(a^n\equiv_m b^n \;\;\forall n \ge 0\)

Folgerung 10:

Kongruenzen können bis auf die Division, wie normale Gleichungen umgeformt werden.

Beispiel:

\begin{align*} x-4 &\equiv_7 6\\ x &\equiv_7 6+4\\ x &\equiv_7 3 \end{align*}

Zu tun

Beispiel: durch 3 teilbar

Divisions Alternative:

Die oben genannten Rechenregeln erlauben keine herkömmliche Division. Es gilt z.B \(6=2*3\equiv 10=2*5\;(mod\,4)\). Beide Seiten enthalten den Faktor 2. Teilt man jedoch beide Seiten durch 2, gilt die Kongruenz nicht mehr. Allerdings kann in bestimmten Fällen ein Faktor durch eine entsprechende Multiplikation entfernt werden.

Beispiel:

\begin{align*} 32 &= 2*2*2*2*2\equiv 22=2*11 \pmod 5\\ &\Leftrightarrow 2*2*2*2*(2*3)\equiv (2*3)*11\pmod 5\\ &\Leftrightarrow 2*2*2*2*1\equiv 1*11\pmod 5\\ \end{align*}

Hinweis: \(2*3 \mod 5 = 1\)

Definition 10: Inverses

Ein Faktor \(x\in \mathbb{Z}_m\) (Def. 3: mögliche Reste) für den gilt \(a*x\equiv 1\pmod m\) nennt man Inverses zu a modulo m. Man schreibt für x dann \(a^{-1}\).

Definition 11: teilerfremde Menge

Die Menge der zu m teilerfremden Zahlen wird als \(Z_m^*\) bezeichnet. \(Z_m^*\subseteq Z_m\)

Beispiel:

\(Z_2^*=\{1\}\), \(Z_3^*=\{1,2\}\), \(Z_4^*=\{1,3\}\), \(Z_5^*=\{1,2,3,4\}\), \(Z_6^*=\{1,5\}\)

Theorem 6:

\(a \perp m \Rightarrow \exists! z\in Z_m^*: z=a^{-1}*b \pmod m\)

Hinweis: \(\exists! z\in Z_m^* \widehat{=}\) „Es gibt genau ein z in \(Z_m^*\)“. D.h. z ist eindeutig.`

Beweis:

1. Zeigen, dass eine Lösung existiert

   \begin{align*} &\exists a^{-1}: a*a^{-1}\equiv 1\pmod m \Rightarrow d\in \mathbb{Z}:a*a^{-1} = todo (d*m+1)\pmod m\\ &\Rightarrow 1\equiv todo a*a^{-1}-d*m.\\ \\ &a\perp m \overset{Folgerung 6}{\Rightarrow} ggT(a,m)=1 \\ &\overset{Theorem 2}{\Rightarrow} \exists \text{ eine Linearkombination der Form: }\,1=c*a+d*m\\ \\ &\text{Ersetze: } c=a^{-1}\text{ und } d=-d \Rightarrow 1=a*a^{-1}-d*m \\ &\Rightarrow \text{Da c und d mittels des euklidschen Algorithmus berechnet werden können, }\\ &\text{muss mindestens eine Lösung existieren, die Kongruent zu c in } Z_m \text{ ist.} \end{align*}

2. Zeigen, dass die Lösung eindeutig ist

   \begin{align*} &\text{Angenommen es gibt die Lösungen } e,f\in Z_m. \text{Dann muss gelten: }\\ &a*e\equiv b\equiv a*f \pmod m \\ &\Leftrightarrow a^{-1}*a*e\equiv a^{-1}*b\equiv a^{-1}*a*f\pmod m\\ &\Leftrightarrow e\equiv a^{-1}*b\equiv f\pmod m\\ &\Leftrightarrow e\equiv f\pmod m\\ \end{align*}

Hinweise:

• Wenn gilt \(a\not\perp m\), also insbesondere wenn \(ggT(a,m)>1\), gilt das obige Theorem nicht.
• Außerhalb von \(Z_m\) existieren unendlich viele Lösungen

Damit lassen sich nun Kongruenzen der Form \(a*x\equiv b \pmod m\) für \(a\in Z_m^*\) nach x auflösen: \(x\equiv a^{-1}*b \pmod m\)

Zu tun

Beispiel

Folgerung 11:

\(p \text{ prim } \cap a*x\equiv b \pmod p \Rightarrow \forall a: \exists a^{-1}\in Z_m\)

Folgerung 12:

\((a)_{\mod m}^{-1} \in Z_m^*\)

\((a)_{\mod m}^{-1}\widehat{=}\) das Inverse von a modulo m.

Für die Kongruenz \(a*x\equiv b \pmod m\) mit \(a \perp m\) und \(a\in Z_m^*\) lässt sich das Inverse zu a mittels des erweiterten euklidschen Algorithmus errechnen. Vertauscht man die Rollen von \(a\) und \(a^{-1}\) und \(d\) mit \(m\) erhält man durch den erweiterten euklidschen Algorithmus die selbe Linearkombination: \(1=a*a^{-1}+d*m\). Daher gilt, dass auch das Inverse zu a modulo m in \(Z_m^*\) enthalten sein muss.

Simultane Kongruenz:

Eine simultane Kongruenz ganzer Zahlen ist ein System von linearen Kongruenzen.

Betrachten wir nun den Fall, dass zwei lineare Kongruenzen gegeben sind:

\begin{align*} a_1*x&\equiv b_1 \pmod m\\ a_2*x&\equiv b_2 \pmod h\\ \end{align*}

Angenommen es gilt: \(a_1\perp m\) und \(a_2\perp h\). Mithilfe von Theorem 6:

\begin{align*} x&\equiv a_1^{-1}*b_1 \pmod m\\ x&\equiv a_2^{-1}*b_2 \pmod h\\ \end{align*}

Gesucht werden also Werte für x, die modulo m und modulo h gleich sind.

Theorem 7: Chinesischer Restsatz

Sei \(m\perp h\). Für \(a\in Z_m\) und \(b\in Z_h\) haben die beiden Kongruenzen

\begin{align*} x&\equiv a \pmod m\\ x&\equiv b \pmod h\\ \end{align*}

, die eindeutige gemeinsame Lösung:

\[x=(a*h'*h+b*m'*m) \mod m*h\]

Dabei gilt:

\(x\in Z_{mh}\),

\(h'=(h)_{\mod m}^{-1}=\) Inverse zu h modulo m,

\(m'=(m)_{\mod h}^{-1}=\) Inverse zu m modulo h

Zu tun

Beweis

Zu tun

Beispiel

Theorem 8: Verallgemeinerter Chinesischer Restsatz

Gegeben sind die Kongruenzen:

\begin{align*} x&\equiv a_1 \pmod {n_1}\\ x&\equiv a_2 \pmod {n_2}\\ &... x&\equiv a_k \pmod {n_k}\\ \end{align*}

Dabei sind die \(n_i\)’s paarweise teilerfremd. Dann kann man mit \(n=\prod_{i=1}^k n_i\), eine Lösung x wie folgt berechnet werden:

\[x=(\sum_{i=1}^k a_i*(\frac{n}{n_i})_{\mod n_i}^{-1}*\frac{n}{n_i}) \mod n\]

Theorem 9: Eulersche \(\varphi\)-Funktion

Die Eulersche \(\varphi\)-Funktion ist:

\[\varphi(m) = \vert Z_m^*\vert\]

Für p prim gilt:

\[\varphi(m)=m* \prod_{p\mid m}(1-\frac{1}{p})\]

Zu tun

BSP.

Theorem 10: Satz von Euler

Für alle \(n\ge 2\) und alle \(a\in Z_m^*\) ist:

\[a^{\varphi(n)} \equiv 1 \pmod{n}\]

Zu tun

Beweis

Folgerung 13:

Für alle Primzahlen p und \(a\in\{1,...,p\}\) gilt:

\[a^{p-1}\equiv 1 \pmod{p},\]

da nach Theorem 9: \(\varphi(p)=p-1\)

Theorem 11: Kleiner Satz von Fermat

Für eine Primzahl p und eine beliebige ganze Zahl a gilt:

\[a^p\equiv a\pmod{p}\]

Zu tun

RSA