Zusätzlicher Beweisteil - der auf dem Video fehlt

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Vorbemerkung

In der Vorlesung - bzw. auf dem Video haben wir den Satz von Euler schlussendlich so bewiesen, dass wir folgende Kongruenz aufgestellt haben:

k_1*k_2*k_3* \ ...\ *k_{\varphi (m)} \equiv \ ak_1*ak_2*ak_3* \ ...\ *ak_{\varphi (m)} \ mod \ m oder anders ausgedrückt \prod^{\varphi (m) }_{i=1} k_i \equiv \prod^{\varphi (m) }_{i=1} ak_i \ mod \ m 

Dies haben wir dann (nach bekanntem Satz) durch alle teilerfremden k_i dividiert und schlussendlich blieb unsere Behauptung stehen.

Allerdings haben wir das mit der Permutation begründet, nämlich, dass für alle k_i*a erneut ein Element k_i entsteht.

Da ich aber schon lange nichts mehr aufgrund eines Beispieles glaube ;-), versuche ich das ganze hier mal zu beweisen (und hoffe, dass das so funktioniert):

Beweis

Voraussetzung: ggT(a, m) = 1 un alle Teilerfremden Zahlen von m seien als Menge K bezeichnet. Es gilt: Fehler beim Parsen(Syntaxfehler): K = \{k_i \in \mathbb{N} \ | \ 1 \le k \ge m \ \wedge \ ggT(k, m) = 1 }



Behauptung: k_1*k_2*k_3* \ ...\ *k_{\varphi (m)} \equiv \ ak_1*ak_2*ak_3* \ ...\ *ak_{\varphi (m)} \ mod \ m

Wenn wir nun die Permutation zeigen können, dann sind wir fertig, da ak_i \equiv k_j ist.
Bleibt zu zeigen: \forall \ k \in  K \ \exists k \in K: \ ak_i \equiv k_j und ist eindeutig.

Gültigkeit

Weil a eine teilerfremde Zahl mit m ist (gilt nach VSS) gilt auch, dass die sich ein k_o in K findet, mit der Eigenschaft k_o \equiv a \ mod \ m. Jetzt müssen wir nur noch zeigen, dass folgende Eigenschaft gilt:

\{K \setminus \{0\};*\} ist eine abgeschlossene algebraische Struktur.
Es gilt: \overline{k_a}*\overline{k_b} \ = \ \overline{k_a*k_b} Wir wissen (aus den natürlichen Zahlen) dass die Multiplikation zweier teilerfremder Zahlen
ebenfalls eine teilerfremde Zahl ergibt (man überzeuge sich aus der PFZ).
Dies gilt nun auch für die Restklassenmenge K => sie ist abgeschlossen. Bleibt die umkehrbare Eindeutigkeit zu zeigen.

Umkehrbare Eindeutigkeit

Diese ist schnell gezeigt:

Nehmen wir an, dass zwei verschiedene k mit a multipiziert das ein gleiches k produzieren.

Annahme: \ ak_i \ = \ k_x \ und \ ak_j \ = \ k_x

Dann gilt: ak_i \ = \ ak_j und k_i \ = \ k_j

Die ist aber erneut ein Widerspruch zu unserer VSS, da alle k_i voneinander verschieden sind.

Die umkehrbare Eindeutigkeit zeigt sich auf gleichem Wege, man nehme einfach an, dass ak_i zwei verschiedene k_j und k_o ergibt.
--Flo1860 16:47, 8. Jun. 2012 (CEST)