Euler-Phi-Funktion; Beweis |
22.06.2014, 12:20 | SandraK | Auf diesen Beitrag antworten » | ||||||
Euler-Phi-Funktion; Beweis Hallo alle zusammen, w ir haben folgende Aufgabe bekommen: Zeigen Sie, dass für alle natürlichen Zahlen gilt: 1. phi(2n) = phi(n) , falls n ungerade 2. phi(2n) = 2phi(n) , falls n gerade Meine Ideen: phi(n) ist stets eine gerade Zahl. Wenn also n ungerade ist und ich diese Zahl verdopple wie in 1., dann wird sie wieder gerade. Okay verstehe ich, aber wie zeige ich das? Noch zu der Definition von phi(n): phi(n) = n(1-1/p1)...(1-1/pr), wobei p1...pr Primzahlen sind. Wie kann ich in dieser Gleichung jeweils das ungerade bzw. gerade n verdeutlichen? Danke schon mal für eure Tipps! |
||||||||
22.06.2014, 17:03 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||
Hallo, es ist für teilerfremde m,n. (folgt direkt aus dem chin. Restsatz) |
||||||||
22.06.2014, 18:11 | SandraK | Auf diesen Beitrag antworten » | ||||||
Das verstehe ich leider nicht. Wie zeige ich mit dem chinesischen Restsatz die beiden Aussagen? Weil die Eulerfunktion multiplikativ ist folgt phi(mn) = phi (m) mal phi (n), aber das ist ja noch kein Beweis für die Aussagen oben oder? Danke schon mal für deinen Hinweis! |
||||||||
22.06.2014, 18:29 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||
Nein. Das ist die Aussage, dass die Eulerfunktion (zahlentheoretisch) multiplikativ ist.
gar nicht . Die Multiplikativität folgt aus dem chin. Restsatz.
Nein, es ist ja nur ein Hinweis. Musterlösungen gibt's hier aus gutem Grund nicht. |
||||||||
22.06.2014, 20:38 | SandraK | Auf diesen Beitrag antworten » | ||||||
Ich erwarte keine Musterlösung, ich verstehe den Zusammenhang einfach nicht. Trotzdem danke für deine Mühe. |
||||||||
22.06.2014, 22:09 | SandraK | Auf diesen Beitrag antworten » | ||||||
RE: Euler-Phi-Funktion; Beweis Okay zu dem 1. hab ich jetzt: phi(2n) = phi(2) mal phi(n) {Multiplikativität gilt wegen n ungerade und ggt(2,n)=1} = 1 mal phi(n) = phi(n) |
||||||||
Anzeige | ||||||||
|
||||||||
23.06.2014, 09:11 | tmo | Auf diesen Beitrag antworten » | ||||||
Ja, das passt doch. Und die zweite Aussage zeigt man ähnlich. Schreibe mit ungerade und berechne nun und . Man kann die Aussage alternativ übrigens auch recht leicht direkt aus der Definition zeigen: Seien die zu teilerfremden Zahlen zwischen und . Ist gerade, so sind genau die zu teilerfremden Zahlen zwischen und . |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |