Eulersche Funktion

Neue Frage »

02.11.2008, 21:23	Bjoern1982	Auf diesen Beitrag antworten »
Eulersche Funktion Hallo, es sei n=pq mit 2 Primzahlen p und q, $\begin{eqnarray} \varphi(n) \end{eqnarray}$ die eulersche Funktion und c,d natürliche Zahlen mit $\begin{eqnarray} cd \equiv 1\ mod\ \varphi(n) \end{eqnarray}$ Jetzt soll man zeigen, dass für alle natürlichen Zahlen m gilt: $\begin{eqnarray} m^{cd}\equiv m\ mod\ n \end{eqnarray}$ Bei meinem Ansatz ende ich irgendwie nachher in einem Widerspruch: $\begin{eqnarray} cd\equiv 1\ mod\ \varphi(n)<=> cd=k\cdot \varphi(n)+1 \end{eqnarray}$ Also dachte ich man könnte den Satz von Euler benutzen: $\begin{eqnarray} m^{cd}=m^{k\cdot \varphi(n)+1}=(m^k)^{\varphi(n)} \cdot m \end{eqnarray}$ Der 1. Faktor wäre ja dann kongruent zu 1 modulo n, aber nur dann, wenn auch wirklich m^k und n teilerfremd sind, was ja durch ein einfaches Gegenbeispiel schon direkt widerlegt werden kann Was mache ich falsch ? Edit: Ok, oder betrachte ich den Fall wenn m^k und n nicht teilerfremd sind separat und folgere dass m^k dann auf jeden Fall durch n teilbar ist und somit der Ausdruck $\begin{eqnarray} m^{cd}=m^{k\cdot \varphi(n)+1}=(m^k)^{\varphi(n)} \cdot m \end{eqnarray}$ kongruent zu null ist ? Und die rechte Seite (m mod n) der Behauptung wird dann auch automatisch 0 kongruent n weil wenn m^k ein Vielfaches von n ist, dann ist es m ja genauso Gruß Björn
02.11.2008, 22:57	kiste	Auf diesen Beitrag antworten »
Betrachte $\begin{eqnarray} m^{k\varphi(n)+1} = m^{k(p-1)(q-1)}\cdot m \end{eqnarray}$ seperat kongruent modulo p und modulo q. Benutze dann den chinesischen Restsatz.
02.11.2008, 23:01	Bjoern1982	Auf diesen Beitrag antworten »
Dank dir, den Ansatz werde ich gleich (oder morgen) auch nochmal testen. Hast du meine (zahlreichen) Edits noch bemerkt und wenn ja, was sagst du zu meiner Argumentation ?
02.11.2008, 23:19	kiste	Auf diesen Beitrag antworten »
Zu deinem Edit: Es muss nicht unbedingt kongruent 0 sein. Es gibt ja folgende Fälle: $\begin{eqnarray} n \| m \end{eqnarray}$ : Da ist es kongruent 0 $\begin{eqnarray} p \| m \land q \not \| ~m \end{eqnarray}$ bzw. den dazu symmetrischen Fall und $\begin{eqnarray} (n,m) = 1 \end{eqnarray}$ : Hier funktioniert deine Argumentation nicht mehr, nur beim teilerfremden Fall funktioniert dein Beweis mit dem Satz von Euler.
03.11.2008, 23:14	Bjoern1982	Auf diesen Beitrag antworten »
Hmm schade eigentlich Kannst du deine Idee mit dem Chinesischen Restsatz noch weiter ausführen, ich bekomme es leider nicht hin
03.11.2008, 23:15	kiste	Auf diesen Beitrag antworten »
Es ist $\begin{eqnarray} m^{k\varphi(n)+1} \equiv m \mod p \end{eqnarray}$ und $\begin{eqnarray} m^{k\varphi(n)+1} \equiv m \mod q \end{eqnarray}$ . Nach dem Chinesischen Restsatz also auch $\begin{eqnarray} m^{k\varphi(n)+1} \equiv m \mod pq \end{eqnarray}$ . Die oberen beiden Kongruenzen musst du jetzt nur noch zeigen
Anzeige

03.11.2008, 23:46	Bjoern1982	Auf diesen Beitrag antworten »
Ok, dann kann ich aber so argumentieren wie oben um die beiden Kongruenzen zu zeigen oder ? Nur dass ich wegen mod p und mod q lieber mit dem kleinen Fermat argumentieren sollte, stimmts ?
03.11.2008, 23:48	kiste	Auf diesen Beitrag antworten »
Was du mit wie oben argumentieren genau weißt verstehe ich jetzt nicht. Aber ja meine Lösung verwendet ebenfalls den kleinen Fermat.
03.11.2008, 23:54	Bjoern1982	Auf diesen Beitrag antworten »
Ok, dann schreibe ich es mal ausführlicher und hoffe dass wir dasselbe meinen $\begin{eqnarray} m^{k\varphi(n)+1}=(m^{k \cdot (q-1)})^{p-1} \cdot m \equiv m \mod p \end{eqnarray}$ Und das ist deshalb so, da $\begin{eqnarray} a=(m^{k \cdot (q-1)}) \end{eqnarray}$ kongruent 1 mod p ist falls ggT(a,p)=1 und falls nicht enthält a in jedem Fall p als Faktor, wodurch das dann auf 0 kongruent 0 mod p hinausläuft. Siehst du das genauso ? (Analog mit mod q)
03.11.2008, 23:58	kiste	Auf diesen Beitrag antworten »
Verstehe deine Argumentation nicht ganz. Ich habe $\begin{eqnarray} (m^{p-1})^{k(q-1)} m \equiv 1^{k(q-1)} m \equiv m \mod p \end{eqnarray}$
04.11.2008, 00:06	Bjoern1982	Auf diesen Beitrag antworten »
Ja, aber das gilt durch wiederum nur wenn m und p teilerfremd sind, was ja nicht zwingend sein muss...
04.11.2008, 00:10	kiste	Auf diesen Beitrag antworten »
Ah okay, ich verstehe was du meinst. Ja das macht aber auch nicht den in diesem Fall muss eben m=p*l sein was nicht im Widerspruch zur zu zeigenden Aussage steht da dann eben das ganze kongruent 0 ist. Ich denke ich stimme mit dir jetzt überein.
04.11.2008, 00:12	Bjoern1982	Auf diesen Beitrag antworten »
Yeeah...vielen Dank für deine Hilfe

Neue Frage »

Antworten »

Eulersche Funktion

Verwandte Themen