Kongruenz Module m ${\mathbb{Z}}_{\mathbb{N}}$

part of [[103.00_anchor_math]]

Seien $n,q\in \mathbb{Z},m\in \mathbb{N},r\in \{0,1,\dots m-1\}$

1. Wir definieren $r$ als Rest von n modulo m, Notation mit n mod m und m heißt das Modul
2. Im Fall $r=0$ sagen wir: n ist durch m teilbar –> m teilt n (4:2..) und notieren dies mit $m|n$ m, teilt n
3. Gilt für $n_1,n_2\in \mathbb{Z}$: Dann ist $n_{1}modm=n_{2}modm$ –> das heißt beide sind durch m teilbar und sie ergeben in der Betrachtung den gleichen Rest = 0. Dann benennen wir $n_1\equiv n_2$ als kongruent

Bemerkung zu Kongruenz ::

$n_1\equiv n_2\mathrm{mod}m⟺\exists q_1,q_2\in \mathbb{Z},r\in \{0,\dots ,m-1\}$
das heißt $n_1=q_1\ast m+r$ und $n_2=q_2\ast m+r$ $⟺n_1-n_2=(q_1-q_2)\ast m$ das heißt also $m\text{teilt}(n_1-n_2)$. Also

Beispiele :

$7mod3=1$ $10\mathrm{mod}3=1$ $37mod7=237:7=35+2⟹2$ ($-10\mathrm{mod}3=-10\mathrm{mod}3="-1"⟶3-1=2$)

Kongruenz als Äquivalenzrelation :

Ist ein Modul $m\in \mathbb{N}$ fest vorgegeben, so ist auf $\mathbb{Z}$ eine Äquivalenzrelation durch: $n_1\sim n_2⟺n_1\equiv n_2\mathrm{mod}m$ Die Zahlen $0,1,\dots ,m-1$ bilden dafür ein vollständiges Repräsentatensystem

Satz von Euler:

$\forall a,n\in \mathbb{N}$ mit ggT$(a,n)=1$ gilt: $$a^{|{\mathbb{Z}}_n^{\ast }|}\equiv 1(\mathrm{mod}n)$$ Folglich lässt sich daraus resultieren: $a^{|{\mathcal{Z}}_n^{\ast }|+1}\equiv 1\cdot amodn$ Also wenn etwa ${\mathcal{Z}}_7$ gilt, dann ist $a^7\equiv 1\cdot a=a$

${\mathbb{Z}}_m,\oplus ,\odot$

Gegeben sei ein fester Modul $M\in \mathbb{N}$. Auf den Resten ${\mathbb{Z}}_m:=\{0,1,\dots ,m-1\}$ definieren wir die Verknüpfungen $\oplus ,\odot$ wie folgt: $\odot$ $r_1\odot r_2=)r_1\ast r_2\mathrm{mod}m$ also eine Multiplikation, welche anschließend der Modulooperation gefolgt ist. $\oplus$ $r_1\oplus r_2:=(r_1+r_2\mathrm{mod}m)$ für $r_1,r_2\in {\mathbb{Z}}_m$

Beispiel : ${\mathbb{Z}}_5$

${\mathbb{Z}}_m=\{0,1,2,3,4\}$– alle Reste der Menge mod 5 $2\oplus 0=2,2\oplus 1=3,2\oplus 2=4,2\oplus 3=0,2\oplus 4=6\mathrm{mod}5=1$ selbiges giltauch für $\odot$ $2\odot 0=0$ $2\odot 1=2$ $2\odot 2=4$ $2\odot 3=6=1$ $\dots$

Unter der Betrachtung des zuvor definierten Repräsentatensytem mit den angegebenen Verknüpfungen $\oplus ,\odot$ können wir nun nach Inversen, neutralen Elementen suchen:

Inverses in ${\mathbb{Z}}_m$

Bezüglich $\oplus$ besitzt jedes Element in ${\mathbb{Z}}_m$ ein Inverses.

$-0=0,$ denn $0\oplus 0=0$!

Am Beispiel von ${\mathbb{Z}}_5$ können wir es wie folgt bestimmen: $-1=4$ denn $1\oplus 4=0$ $-2=3$ $-3=2$ $-4=1$ Möchten wir nun das Inverse für die Multiplikation $\odot$: $1^{-1}=1⟹1\odot 1=1$ $2^{-1}=3⟹2\odot 3=6=1\square$ $3^{-1}=2⟹3\odot 2=1$ $4^{-1}=4⟹4\odot 4=16=1$

Neutrales Element in ${\mathbb{Z}}_m$:

Das inverse Element ist definiert mit: 1. $\oplus =0$ 2. $\odot =1$

und kann wie obige mit dem Inversen berechnet werden. Dabei ist relevant, dass wir für alle die Gleichung $x\oplus \vee \odot y=1\vee 0$ –> Also das gleiche Vorgehen, wie oben beschrieben. in $\mathbb{Z}$ demnach : $1\oplus 4=0$ $2\oplus 3=0$ $3\oplus 2=0$ $4\oplus 1=0$

Bemerkung Unterschied mod :

Es besteht ein Unterschied zwischen $a\mathrm{mod}m$ und $a\equiv bmodm$, denn $a\mathrm{mod}m$ $\in mathbb{Z}_m=\{0,\dots ,m-1\}$ und $a\equiv b\mathrm{mod}m$ ist $\equiv \mathrm{mod}m$ , also eine Äquivalenzrelation auf $\mathbb{Z}$, die eine Verknüpfung von zwei Zahlen $a,b\in \mathbb{Z}$ angibt. Es ist also eine Teilmenge : $\mathbb{Z}\times \mathbb{Z}$

Rechenregeln mit Modulo:

Seien $a\equiv a^{{}^{\prime }}\mathrm{mod}m$ und $b\equiv b\mathrm{mod}m$ mit $a,a^{{}^{\prime }},b,b^{{}^{\prime }}\in \mathbb{Z}\wedge m\in \mathbb{N}$

Dann gilt für folgende Verknüpfungen : $a+\vee -b\equiv (a^{{}^{\prime }}+\vee -b^{{}^{\prime }})\mathrm{mod}m$ denn sie sind ja schon equivalent zueinander und somit auch die Verknüpfung der anderen Terme $a^{{}^{\prime }},b^{{}^{\prime }}$ $a\ast b\equiv (a^{{}^{\prime }}\ast b^{{}^{\prime }})\mathrm{mod}m$

Weiterhin gilt : $(a+b)\mathrm{mod}m⟺(a\mathrm{mod}m)+(b\mathrm{mod}m)\mathrm{mod}m$ oder $(a\mathrm{mod}m)-(b\mathrm{mod}m)\mathrm{mod}m$ $(a\ast b)\mathrm{mod}m⟺((a\mathrm{mod}m)\ast (b\mathrm{mod}m))\mathrm{mod}m$ Also wir können eine Konkatenation $\mathrm{mod}m$ einfacher anwenden, wenn wir die einzelnen Zahlen der Konkatenation zuvor mit $\mathrm{mod}m$ verkleinern bzw. anpassen.

Die Sätze können bewiesen werden, indem $a\mathrm{mod}m\equiv a(\mathrm{mod}m)$ und der obere Teil aus den Rechenregeln

Diese Rechenregeln können für $+,\ast$ in $\mathbb{Z}$ und $\oplus ,\odot$ in ${\mathbb{Z}}_m$ angewandt werden!

Beispiele ::

Welchen Rest lässt $214934^{2023}$ bei DIvison durch 7 $\equiv \mathrm{mod}7$

Idee: Die Zahl so in eine kleinere Summe aufteilen, dass möglichst viele Teile $\mathrm{mod}7$ sind, d.h.

$214934^{2023}\equiv (210000+4900+35-1{)}^{2023}\equiv (-1{)}^{2023}\equiv (-1)\equiv 6$

ggT, teilerfremd ::

Seien $a_1,\dots ,a_n\in \mathbb{Z}$

1. Ist mindestens ein $a_i\ne 0$ so ist der größte gemeinsame Teiler (ggT) die größte natürliche Zahl, die alle $a_1,\dots ,a_n$ teilt.

Wir schließen 0 aus, weil jede Zahl 0 als Teiler hat und somit die Aussage trivial und nicht notwendig wäre..

2. Ist der ggt von $a_1\dots ,a_n=1$ so heißen $a_1,\dots ,a_n$ teilerfremd

1 ist ebenfalls der Teiler von allen Zahlen, wodruch wir folgern können, dass etwas keinen ggt hat, wenn es 1 ist.

Beispiele ::

$ggT(20,24)=4,$ da $20|4\wedge 24|4⟹4$ $ggT(20,21)=1$, da kein gemeinsamer größter Teiler, außer 1 zu finden ist.

Euklidischer Algorithmus ::

Um effizient bzw. schnell berechnen zu können, wie der ggT von zwei Zahlen ist, kann der (erweiterte) euklidische Algorithmus angewandt werden, um diesen mit einem Algorithmus zu berechnen.

Er kann also füý $a,b\in \mathbb{Z}$ ganze Zahlen $s,t$ mit ggT(a,b) = $s\cdot a+t\cdot b$

Beispielsweise mit (20,24) $=4=(-1)\cdot 20+1\cdot 24$

Satz :

Sei $m\in \mathbb{N}$

1. $({\mathbb{Z}}_m,\oplus )$ist eine abelsche Gruppe
2. $({\mathbb{Z}}_m,\odot )$ ist im Allgemeinen keine Gruppe –> nicht unmöglich, aber selten der Fall //

Beweis des Satzes ::

Für die $({\mathbb{Z}}_m,\oplus )$ muss bewiesen werden :

1. Nach früheren Definition muss die Abgeschlossenheit gelten $(a\oplus b\in \{a_1,\dots ,m-1\}\text{definiert u¨ber Mod})$
2. Assoziativgesetzt und Kommutativität gilt gemäß früherer BEtrachtung [[math2_permutationen#Abgeschlossenheit von $S_n$|Abgeschlossenheit ]]
3. neutrales Element ist $0:a\oplus 0=(a+0)\mathrm{mod}m=a$ sowei $0:0\oplus a=(0+a)\mathrm{mod}m$
4. Inverses Element für $a\in {\mathbb{Z}}_m$ ist in dem Falle $\begin{array}{c}0,\text{falls }a=0\\ m-a,\text{falls}a\ne 0\end{array}$ denn dann gilt jeweils: $a\oplus (m-a)\equiv (a+(m-a))\mathrm{mod}m\in \{0,m-1\}\equiv m\mathrm{mod}m$ $\equiv 0\mathrm{mod}m$

Beispielsweise in ${\mathbb{Z}}_{15}$

Das inverse bzgl. $\oplus$ für $9:15-9=6⟹-9=6\in {\mathbb{Z}}_{15}$

Weiter betrachten wir noch, dass im Allgemeinen keine Gruppe möglich ist, mit $\odot$

1. wir Zeigen das neutrale Element: Es muss bezüglich $\odot$ 1 sein, da $1\odot a=(1\dot{a})\mathrm{mod}m\equiv (a\dot{)}\mathrm{mod}m\equiv a\mathrm{mod}m\forall a\in {\mathbb{Z}}_m$
2. Die Betrachtung des inversen Element wird Fehler aufwerfen:: $0\in {\mathbb{Z}}_m$ besitzt keine Inverse bezüglich $\odot$ - denn dann müsse gelten, dass: $\exists a\in {\mathbb{Z}}_m,(0\dot{a})\mathrm{mod}m{=}^{!}1$ was nicht existiert Dennoch können wir betrachten, dass diverse Elemente in der Menge invertierbar sind: $x\in {\mathbb{Z}}_m\text{ ist invertierbar}⟺\exists y\in {\mathbb{Z}}_m:x\odot y=1$ $⟺\exists y\in {\mathbb{Z}}_m:(x\cdot y)modm=1$ $⟺\exists y,q\in {\mathbb{Z}}_m:(xy)=q\cdot m+1$ $⟺\exists y,q\in {\mathbb{Z}}_m:xy+(-q)\cdot m=1$ $⟺ggT(x,m)=1$ Also folgern wir daraus: In ${\mathbb{Z}}_m$ sind nur die teilerfremden Elemente zu $m$ invertierbar.

Beispiele::

In der Betrachtung können wir schnell für ${\mathbb{Z}}_4$ sagen, dass wir nur 1 und 3 invertieren können, da 2 nicht teilerfremd zu 4 ist $ggT(2,4)=2⟺2$ nicht invertierbar! Unter Anwendung von ${\mathbb{Z}}_5$ können wir drauß schließen, dass sich alle Elemente, also $\{1,2,3,4\}$ invertieren lassen, da sie teilerfremd zu 5 sind.

Sofern wir also eine Menge mit ${\mathbb{Z}}_p,$ wobei $p=\text{Primzahl}$ , dann sind alle Elemente davon invertierbar, da $p$ teilerfremd zu allen, außer 1 und sich selbst ist.

Bemerkung $({\mathbb{Z}}_m^{\ast },\phi (m))$

Wir können eine neue Gruppe über ${\mathbb{Z}}_m$ definieren, die bezüglich der Multiplikation abgeschlossen ist. ${\mathbb{Z}}_m^{\ast }:=\{x\in {\mathbb{Z}}_m|ggT(x,m)=1\}$ –> also wir garantieren, dass die Zahlen invertierbar sind und lassen alle die heraus, die nicht dazugehören. Da sie eine Teilmenge von ${\mathbb{Z}}_m^{\ast }\subseteq {\mathbb{Z}}_m$ ist und alle Elemente entfernt, die bezüglich $\odot$ nicht invertierbar sind, ist es eine Gruppe.

Weiterhin definieren wir jetzt die eulersche $\phi$-Funktion als : $\phi :\begin{array}{c}\mathbb{Z}⟹\mathbb{N}\\ m⟼\phi (m):=|{\mathbb{Z}}_m^{\ast }|\end{array}$ $\phi (m)$ ist also die Anzeige, der zu m teilerfremdne Zahlen zwischen 1, und $m$.

Beispiele ::

${\mathbb{Z}}_3^{\ast }=\{1,2\},\phi (3)=2$ –> gibt also die menge der teilerfremden Elemente der Menge an ${\mathbb{Z}}_4^{\ast }=\{1,3\},\phi (4)=2$ –> 1,3, mehr nicht ${\mathbb{Z}}_8^{\ast }=\{1,3,5,7\},\phi (8)=4$ –> Menge des Betrages 4 // ${\mathbb{Z}}_p^{\ast }=\{1,2\dots ,p-1\},\phi (p)=p-1$, sofern $p$eine Primzahl ist

Untergruppen $(G\cdot )$

Sei $(G,\cdot )$ eine Gruppe mit $\varnothing \ne U\subseteq G$ eine Teilmenge. $U$ heißt jetzt eine Untergruppe von G, also $|U|,\le |G|$ falls U bzgl. $\cdot$ selbst eine Gruppe ist.

Aus dieser Definition gilt dann:

• $\forall u,v\in U$ ist $u\cdot v\in U$ –> Abgeschlossenheit
• $e$ von G ist auch $e$ von U –> gleiches Neutrale Element!
• Inversen in $U$ sind die selben wie in $G$

Beispiele Untergruppen :

1. $(\mathbb{Z},+)\le (\mathbb{Q},+)\le (\mathbb{R},+)$
2. $(\{-1,1\}\cdot )$ –> Inverses existiert, ist abgeschlossen, und weist neutrales Element auf(1) Weiterhin : $(\{-1,1\}\cdot )\le ((\mathbb{Q}\setminus \{0\},\cdot ))\le (\mathbb{R}\setminus \{0\},\cdot )$
3. die kleinste Gruppe können wir beschreiben mit: $(\{e\},\cdot )$ ist eine Untergruppe jeder beliebigen Gruppe mit der Verknüpfung $\cdot$und dem neutralen Element $e$
4. $\pi =\left[\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right]\in S_3$ ; generieren wir dafür eine Gruppe
   1. $\{\pi ,ϵ\}\le S_3$, denn unter der Betrachtung der Gruppenaxiome: $\pi \cdot \pi =\left[\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right]=ϵ$ –> inverses, was das neutrale Element bildet. $\pi ={\pi }^{-1}$ ist sein eigenes inverses Element.