Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Eulersche-Phi-Funktion nicht teilerfremden Zahlen

Eulersche-Phi-Funktion nicht teilerfremden Zahlen

Universität / Fachhochschule

Algebraische Zahlentheorie

Tags: Algebraische Zahlentheorie, eulersche Phi-Funktion

huida aktiv_icon

01:54 Uhr, 13.02.2019

Guten Tag zusammen!

Ich bräuchte Eure Hilfe bei einer Aufgabe.

Es geht um den Beweis der verallgemeinerten Eulerschen-Phi-Funktion.

φ (m \cdot n) = \frac{φ (m) \cdot φ (n) \cdot g}{φ (g)}

und g=ggt(m,n) mit

g \geq 1

Als Hinweis steht: Führen sie den Beweis per Induktion über die gemeinsamen Primteiler.

IA: keine gemeinsamen Primteiler, so ist ggt(m,n)=1 und es passt.

IS: Haben gemeinsame Primteiler so ist ggt(m,n)>1

Es existieren

k, l, e, f \in Z

mit

m = p^{e} \cdot k

und

n = p^{f \cdot} l

φ (m \cdot n) = φ (p^{e} \cdot k \cdot p^{f \cdot} l) = φ (p^{e + f}) \cdot φ (k \cdot l)

=(IV)

φ (p^{e + f}) \cdot \frac{φ (k) \cdot φ (l) \cdot g}{φ (g)} = p^{e + f - 1} \cdot (p - 1) \cdot \frac{φ (k) \cdot φ (l) \cdot g}{φ (g)} = \frac{p^{e} \cdot p^{f}}{p} \cdot (p - 1) \cdot \frac{φ (k) \cdot φ (l) \cdot g}{φ (g)} = ... = \frac{φ (k) \cdot φ (l) \cdot g}{φ (g)}

Ich komm nicht mehr weiter. Meine Tutorin meinte man könne mit

\frac{φ (g)}{φ (g)}

erweitern. Aber dennoch schaffe ich es nicht das linke Produkt wegzukürzen.

Kann mir jemand dabei helfen? Oder einen andere Lösung zeigen wie es geht. Es ist nicht "zwingend" erfordelich es per Induktion zu machen

Grüße :-D)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

HAL9000

09:22 Uhr, 13.02.2019

Wenn schon Crossposting, dann bitte erwähnen: www.matheboard.de/thread.php?threadid=590189

ermanus aktiv_icon

10:16 Uhr, 13.02.2019

Hallo,
ich würde es nicht mit vollständiger Induktion beweisen,
sondern die Darstellung

φ (a) = a \cdot \prod_{p ∣ a} (1 - \frac{1}{p})

verwenden.
Es ist

φ (m) \cdot φ (n) = m \cdot \prod_{p ∣ m} (1 - \frac{1}{p}) \cdot n \cdot \prod_{p ∣ n} (1 - \frac{1}{p}) (*)

.

Betrachten wir die beiden Produkte über die Primteiler, so sehen wir,
dass genau die Primteiler von

g

sowohl im ersten als auch im zweiten
Produkt vorkommen. Da diese aber als Primteiler von

m n

nur einmal gezählt
werden, bekommt man folgende Gleichung:

\prod_{p ∣ m} (1 - \frac{1}{p}) \cdot \prod_{p ∣ n} (1 - \frac{1}{p}) = \prod_{p ∣ m n} (1 - \frac{1}{p}) \cdot \prod_{p ∣ g} (1 - \frac{1}{p})

(*)

liefert also:

φ (m) \cdot φ (n) = m n \cdot \prod_{p ∣ m n} (1 - \frac{1}{p}) \cdot g \cdot \prod_{p ∣ g} (1 - \frac{1}{p}) \cdot g^{- 1} =

= φ (m n) \cdot φ (g) \cdot g^{- 1}

.

Gruß ermanus

huida aktiv_icon

16:21 Uhr, 13.02.2019

Sorry HAL9000.

Danke ermanus für deine Hilfe. Soweit kann ich das ganze nachvollziehen.

"Betrachten wir die beiden Produkte über die Primteiler, so sehen wir,
dass genau die Primteiler von

g

sowohl im ersten als auch im zweiten
Produkt vorkommen. Da diese aber als Primteiler von mn nur einmal gezählt
werden, bekommt man folgende Gleichung:"

Die Aussage ist mir klar. Was mit noch unklar ist, ist der letzt Umformungsschritt. Mir ist bewusst das

p | m

und

p | n

daraus folgt, dass auch

p | m n

. Sowie das

p | g

auch klar, da

p

ein gemeinsamer Primteiler von

m

und

n

ist. Wieso kann man den letzten Umformungsschritt so aufschreiben? Also Produkt über p|mn und das Produkt über

p | g

.

Und das

\frac{g}{g}

ist bloß eine Erweiterung um auf die gewünschte Form zu kommen. Korrekt?

Grüße :-)

ermanus aktiv_icon

16:41 Uhr, 13.02.2019

Meinst du die Produktegleichung

\prod_{p ∣ m} (1 - \frac{1}{p}) \cdot \prod_{p ∣ n} (1 - \frac{1}{p}) = \prod_{p ∣ m n} (1 - \frac{1}{p}) \cdot \prod_{p ∣ g} (1 - \frac{1}{p})

huida aktiv_icon

17:11 Uhr, 13.02.2019

Ja genau. Nur die rechte Seite.

ermanus aktiv_icon

17:29 Uhr, 13.02.2019

Damit ich nicht am Formeleditor zugrundegehe,
schreibe ich die Produkte nun mal als
P(m), P(n), P(mn) und P(g).
Um die Gleichung P(m)P(n)=P(mn)P(g) zu beweisen,
müssen wir nur schauen, ob für jede Primzahl p
der Faktor (1-1/p) links und rechts gleichhäufig vorkommt;
denn dann sind die beiden Seiten doch offenbar gleich.
1. Ist p weder Teiler von m noch von n, dann kommt der Faktor (1-1/p)
links und rechts nullmal vor.
2. Ist p ein Teiler von m, aber nicht von n,
dann kommt der Faktor (1-1/p) einmal in P(m), aber nicht in P(n) vor,
also einmal in der linken Seite. Auf der rechten Seite kommt er einmal
in P(mn) vor, aber nicht in P(g), da p kein gemeinsamer Teiler
von m und n ist, also kommt er auch genau einmal in der rechten Seite vor.
3. Ist p ein Teiler von n, aber nicht von m, siehe 2.
4. Ist p ein Teiler von m und von n, also ein gemeinsamer Teiler von
m und n, dann kommt (1-1/p) einmal in P(m) und einmal in P(n) vor,
also zweimal auf der linken Seite, in P(mn) kommt er einmal vor,
und da p gemeinsamer Primteiler von m und n ist, ist p
auch ein Teiler von g, d.h. (1-1/p) kommt auch in P(g) einmal vor, also
kommt (1-1/p) insgesamt 2-mal auf der rechten Seite vor.
Damit ist die Gleichung bewiesen.

huida aktiv_icon

17:37 Uhr, 13.02.2019

Ahh na klar! Danke dir für die Hilfe ermanus. Glaubst du dass ich diesen Schritt auch so erklären muss oder würde das anreihen der Umformungen reichen?

ermanus aktiv_icon

17:41 Uhr, 13.02.2019

Das kommt auf die Leserschaft oder Zuhörerschaft an ;-)
Sollte es sich dabei um MathematikerInnen handeln, kannst du
mein Pamphlet einfach übernehmen.

huida aktiv_icon

19:41 Uhr, 13.02.2019

Kann es sein, dass du dich vertippt hast?
Am Ende von deinem Ersten Post kommst du nicht auf das gewünschte Ergebnis.

Es ist