Eulersche Phi-Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es ist zu beweisen,dass für ggT(m,n)=1
[mm] \phi (mn)=\phi [/mm] (m) [mm] \* \phi [/mm] (n)
gilt.
|
Hallo,
ich bin Schüler der 13Klasse und schreibe gerade meine Facharbeit über die eulersche [mm] \phi [/mm] -funktion.
Nun habe ich ein Problem: ich bekomme den Beweis, dass für ggT(m,n)=1
Multiplikativität gilt nicht hin.
Es wäre nett wenn ihr mir da etwas helfen könntet.Allerdings bitte ich darum, zu beachten dass ich kein Mathestudent bin und deswegen eine einfache erklärung brauche ^^ d.h. ohne Verwendung von Restklassen und Ringen.
Mein Ansatz:
ggT(x,m)=1
ggT(a,m)=1
deswegen
x [mm] \equiv [/mm] a (mod m)
und
ggT(x,n)=1
ggT(b,n)=1
deswegen
x [mm] \equiv [/mm] b (mod n)
Nun dachte ich mir kann man mit dem Chinesischen Restsatz weiterkommen ich hab mich auch bezüglich des CR nformiert,allerdings bekomme ich das irgendwie nicht hin...
Danke für eure Hilfe!
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
[http://www.uni-protokolle.de/foren/viewtopic.php?p=1655600#1655600]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:05 Mo 10.11.2008 | | Autor: | PeterB |
Ok, ich versuche einfach mal eine Elementare Sprache zu benutzen, der Beweis ist der gleiche, wie mit den Restklassenringen (Nur das man da eine andere Version des Cinesischen Restsatzes braucht.)
Wenn du Rückfragen hast schreib einfach.
Also, seien $m$ und $n$ teilerfremd. Und sei [mm] $0\leq a\leq [/mm] mn$ wann ist $a$ jetzt Teilerfremd zu $mn$? Die Antwort ist: Genau falls $a$ Teilerfremd zu $n$ und $m$ ist. (Warum?)
Ob nun $a$ teilerfremd zu $n$ ist hängt aber nur von seinem Rest modulo $n$ ab. (Der Rest bei Division durch $n$) (Warum? Siehe Euklidischer Algorithmus)
Genauso hängt das ggT von $a$ mit $m$ nur von dem Rest modulo $m$ ab.
Jetzt kommt der Chinesische Restsatz ins Spiel: Für jedes Paar $(b,c)$ von einer Zahl $b<n$ und einer Zahl $c<m$ gibt es genau eine Zahl $a<nm$ s.d. $b$ der Rest von $a$bei der Division durch $n$ ist und $c$ der Rest von $a$ bei der Division durch $m$.
Es Verbleibt noch ein bisschen Kombinatorik:
[mm] $\phi$(mn)=#{a|a
[mm] #{(b,c)|b
Dabei bedeutet # "Anzahl der Elemente in der Menge" und die Menge {a|a<mn,ggT(a,mn)=1} bedeutete alle nicht negativen ganzen Zahlen a s.d. a<mn und ggT(a,mn)=1 usw..
Ich habe noch ein paar Lücken gelassen, vielleicht kannst du die ja selbst füllen.
Gruß
Peter
|
|
|
|
