Euler-Phi-Funktion; Beweis

Neue Frage »

SandraK Auf diesen Beitrag antworten »
Euler-Phi-Funktion; Beweis
Meine Frage:
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!
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

es ist für teilerfremde m,n.
(folgt direkt aus dem chin. Restsatz)
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!
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Weil die Eulerfunktion multiplikativ ist folgt phi(mn) = phi (m) mal phi (n),

Nein. Das ist die Aussage, dass die Eulerfunktion (zahlentheoretisch) multiplikativ ist.

Zitat:
Wie zeige ich mit dem chinesischen Restsatz die beiden Aussagen?

gar nicht verwirrt . Die Multiplikativität folgt aus dem chin. Restsatz.

Zitat:
ber das ist ja noch kein Beweis für die Aussagen oben oder?

Nein, es ist ja nur ein Hinweis. Musterlösungen gibt's hier aus gutem Grund nicht.
SandraK Auf diesen Beitrag antworten »

Ich erwarte keine Musterlösung, ich verstehe den Zusammenhang einfach nicht.
Trotzdem danke für deine Mühe.
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)
 
 
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 .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »