Wie beweise ich den Satz von Euler?
a^phi(n) mod n ist kongruent zu 1. (wobei die 1 hier nicht der Rest ist oder? Ist ja eine Kongruenz)
Also ist das doch das Gleiche wie a^phi(n) mod n = 1 mod n?
Ich persönlich habe es glaube ich verstanden, aber wie begründe ich das mathematisch korrekt? Das Internet hat mir da bis jetzt nicht weitergeholfen. Ich müsste ja also eigentlich beweisen, dass zwei teilerfremde Zahlen kongruent zu 1 sind oder? Vor allem darf der Beweis nicht zu lang sein.
Ich danke euch schon einmal sehr stark, wenn ihr mir helfen könnt. Das ist so das Hauptding, bei dem ich gerade noch in meiner Seminararbeit hänge.
1 Antwort
Betrachte den Restklassenring Z/nZ (also die Restklassen bezüglich Modulo n)
Dieser Ring enthält genau phi(n) Elemente, die ein Multiplikatives inverse besitzen. Bezeichne diese Elemente mit r_1, r_2 ... r_phi(n)
Sei nun a eine Zahl, für die ggT(a,n)=1 erfüllt. A ist somit Invertierbar.
Wenn du nun jedes der vorherig definierten r_i mit a Multiplizierst, erhälst du eine eine Permutation, also eine Umordnung der r_i, da zum einen a*r_i Invertierbar ist, und a*r_i=a*r_j gilt, genau dann wenn r_i = r_j gilt (da eben a Invertierbar ist) du bekommst also wieder phi(n) verschiedene invertiebare Elemente, also muss {r_1, r_2, ... r_phi(n)} = {a*r_1,...,a*r_phi(n)} gelten (die Elemente der 2. Menge können aber wie gesagt eine andere Reihenfolge haben, die Mengen sind aber gleich).
Somit folgt (das Gleichheitszeichen soll das Kongruenz Zeichen sein)
r_1*...*r_phi(n) = a*r_1*....*a*r_phi(n) (da wie gesagt man durch die Multiplikation mit m die selbe Menge enthält, also bleibt das Produkt gleich)
=r_1*...r_phi(n)*a^phi(n) (Mod n)
Da die r_i Invertierbar sind, kann sie auf beide Seiten kürzen, man erhält dann die Gleichung:
1=a^phi(n) (Mod n)
Wenn r_i Invertierbar ist gibt es ein r_i^-1 sodass r_i*r_i^-1=1 gilt. Du kannst also beide Seiten mit r_i^-1 (mit i gleich 1 bis phi(n)) multiplizieren. Beide Seiten haben dann natürlich immer noch den selben wert. Links und rechts kürzen sich dann die ganzen r_i weg, weswegen links 1 und rechts a^phi(n) übrig bleibt.
Bzw: wenn seien a und b aus der Algebraischen Struktur und x Invertierbar, dann gilt ax=bx genau dann wenn a=b gilt.
Nur noch eine Frage, ansonsten habe ich alles verstanden. Ich bin dir wirklich sehr dankbar. Wieso darf ich nur kürzen, wenn r_i invertierbar, also teilerfremd zu n, ist?