Wir definieren \theta(m):=produkt(p,p\|m,) mit p \in \IP und \theta(1):=1. Mit \Phi(m) bezeichnen wir die Eulersche \phi\-Funktion. Finde alle Lösungen von \Phi(m)=\theta(m)^2\..

\Phi(m)=\theta(m)^2

\Phi(m)=\theta(m)^3

\

Sei m=produkt(p_i^\alpha_i,i=1,n) mit Primzahlen p_i, mit p_i<p_j für i<j, und \alpha_i positiven natürlichen Zahlen.

Dann ist \theta(m)=produkt(p_i,i=1,n). Also gilt entweder ''2 ist kein Teiler von \theta(m)^2 '', dann ist m ungerade; oder aber ''2^2 ist ein Teiler von theta(m)^2, aber nicht 8'', dann ist m gerade.

Weiter ist \Phi(m)=produkt(p_i^(\alpha-1),i=1,n)*produkt(p_i-1,i=1,n).

Da für jede ungerade Primzahl p der Faktor (p-1) durch 2 teilbar ist, folgt aus der Existenz von ungeraden Primfaktoren von m, dass \Phi(m) und damit auch \theta(m)^2, also auch \theta(m) und damit auch m durch 2 teilbar sind.

Für ungerades m kann es also keine ungeraden Primfaktoren geben, d.h. m ist eine ungerade Zweierpotenz, also m=1. Man sieht leicht, dass dies eine Lösung unserer Gleichung ist.

Sei also ab nun m gerade. Dann ist \theta(m)^2 und damit \Phi(m) durch 4, aber nicht durch 8 teilbar. Da jeder ungerade Primfaktor p von m mit dem Faktor (p-1) von \Phi(m) wenigstens einen Faktor 2 dort beiträgt, kann es also höchstens 2 ungerade Primfaktoren von m geben.

Es bleiben also nur noch die drei folgenden Fälle für die Zahl m zu betrachten:
(1): m=2^a, für eine positive ganze Zahl a \(m ist Zweierpotenz\),
(2): m=2^a*p^b, für pos. ganze Zahlen a,b und einer ungeraden Primzahl p \(ein ungerader Primfaktor\) und
(3): m=2^a*p^b*q^c, für pos. ganze Zahlen a,b,c und ungeraden Primzahlen p<q \(zwei ungerade Primfaktoren\).

Diese Fälle wollen wir nun nacheinander betrachten:
zu (1): Hier ist theta(m)^2=2^2 und Phi(m)=2^(a-1), d.h. a=3 bzw. m=8 liefert die einzige Lösung, welche die Probe auch bestätigt.

zu (2): Hier ist theta(m)^2=2^2*p^2 und Phi(m)=2^(a-1)*p^(b-1)*(p-1). Da 2^(a-1)*(p-1) eine nicht durch p teilbare Zahl ist, und p^2, aber nicht p^3 theta(m)^2 teilt, muss also b-1=2 bzw. b=3 sein. Dann folgt daraus aber nach Division durch p^2=p^(b-1), dass 2^2=2^(a-1)*(p-1) gilt, also insbesondere (p-1)<=4 ist.

Der Fall p=3 liefert dann a-1=1 bzw. m=2^2*3^3=108 und p=5 liefert a-1=0 bzw. m=2^1*5^3=250, was die Probe jeweils als Lösung bestätigt.

zu (3): Hier ist \theta(m)^2=2^2*p^2*q^2 und Phi(m)=2^(a-1)*p^(b-1)*q^(c-1)*(p-1)*(q-1).

Da die beiden Faktoren (p-1) und (q-1) auf jeden Fall gerade sind, ist p^(b-1)*q^(c-1)*(p-1)*(q-1) auf jeden Fall schon einmal durch 4 teilbar, d.h. a-1=0 bzw. a=1. Außerdem wissen wir dadurch, dass (p-1)/2 und (q-1)/2 nicht gerade sein dürfen.

Da q>p ist, ist q kein Teiler von p^(b-1)*(p-1)*(q-1), also ist \Phi(m) genau durch q^(c-1), aber nicht durch q^(c) teilbar, d.h. c-1=2 bzw. c=3. Nach Division der Gleichung durch 4*q^2=4*q^(c-1) ergibt ich also:

p^2=p^(b-1)*(p-1)/2*(q-1)/2.

Da das gesamte Produkt nur durch die Primzahl p teilbar ist (da es ja eine Potenz dieser Primzahl ist), gilt dies auch für jeden Faktor. Insbesondere ist auch 0<(p-1)/2<p eine p-Potenz, d.h. (p-1)/2=1 bzw. p=3. Eingesetzt liefert dies:

3^2=3^(b-1)*(q-1)/2.

Aus dem gleichen Grund muss auch (q-1)/2 eine Dreierpotenz sein, aber wegen q>p ist auch (q-1)/2>1, d.h. es bleibt (q-1)/2=3 bzw. (q-1)/2=9. Der erste Fall führt auf q=7 und (b-1)=1, d.h. m=2^1*3^2*7^3=6174, der zweite auf q=19 und b-1=0, d.h. m=2^1*3^1*19^3=41154. Die Probe bestätgit diese Werte jeweils als Lösungen.

zusammengefasst: Genau die positiven natürlichen Zahlen 1; 8; 108; 250; 6174 und 41154 sind Lösungen der Gleichung \theta(m)^2=\Phi(m).

\theta(m):=produkt(p,p\|m,) und \theta(1):=1.
\phi(m)=sum(1,array(d;(d,m)=1),)
Es gelte: \phi(m)=\theta(m)^2
Offensichtlich ist m=1 eine Lösung
Sei nun m=2^n*r mit n>=0 und r ungerade.
Dann ist 
Wegen \phi(m)=m*produkt((p-1)/p,p\|m,) ist dann
m*produkt((p-1)/p,p\|m,)=produkt(p^2,p\|m,)
=>m*produkt((p-1),p\|m,)=produkt(p^3,p\|m,)
Offensichtlich ist m gerade, da sonst die rechte Seite, nicht aber die linke ungerade wäre.
Sei also m=2^n*r mit n>=1 und r ungerade.
=>2^n*r*produkt((p-1),p\|r,)=2^3*produkt(p^3,p\|r,)
=>2^(n-3)*r*produkt((p-1),p\|r,)=produkt(p^3,p\|r,)
Da die rechte Seite nicht durch 2 teilbar ist, darf
2^(n-3)*r*produkt((p-1),p\|r,) nicht durch 2 teilbar sein.
=>n<=3 da p-1 durch 2 teilbar ist.
(1)n=3 =>r=1 => m=8 und dies ist eine Lösung
(2)n=2 =>r=p^k => 1/2*p^k*(p-1)=p^3
Wegen (p-1,p)=1 =>p-1=2 und k=3 => m=108 und dies ist eine Lösung
(3) n=1
Dann ist 
1/4*r*produkt((p-1),p\|r,)=produkt(p^3,p\|r,)
Ist ein p==1(4) folgt
1/4*p^k*(p-1)=p^3 und analog bei (2) ist p-1=4 =>p=5 sowie k=3
Also m=2*5^3=250 und dies ist eine Lösung
Bleibt r=p^k*q^s mit p!=q
=>1/4*(p-1)*(q-1)*p^k*q^s=p^3*q^3
=>0<k,s<=3 und es muß gelten:
(p-1)/2=q^(3-s) und (q-1)/2=p^(3-k)  (\*)
k=s=3 scheidet wegen p!=q aus.
Aus Symmetriegründen genügt es, die Fälle
(k,s)=(1,1);(1,2);(1,3);(2,2);(2,3) zu betrachten
(\*) => p=2*q^(3-s)+1=2*(2*p^(3-k)+1)^(3-s)+1
s=3 =>p=2*1+1=3 =>q=2*3^(3-k)+1
=>m=2*3*19^3=41154 sowie m=2*3^2*7^3=6174 sind Lösungen
s<3 => p=2*(2*p^(3-k)+1)^(3-s)+1>=2*2*p^(3-k)+1=4p^(3-k)+3
=>3-k=0=>k=3 und p=7 und dies war ausgeschlossen.

Fazit:
Die Lösungen sind
1
8=2^3
108=4*3^3
250=2*5^3
6174=2*3^2*7^3 und 41154=2*3*19^3

Sei a \in \IN und a = produkt(p^ a_p,p Primzahl) die Primfaktorzerlegung von a.

Dann gilt für die Phi-Funktion bekanntlich:
\phi(a) = produkt(p(p-1)^(a_p - 1), p Primzahl und a_p != 0)

Sei nun \Theta(a)^2 = \phi(a).

Wenn a keine ungeraden Primfaktoren hat, so gilt offenbar a = 1 oder a = 8.

Sei nun p der größte ungerade Primfaktor von a.
wegen \phi(a) = \Theta(a)^2 kommt p genau dreimal in a vor.

Wir schreiben p = 2^(k_p) u + 1 mit u ungerade. Es gilt k_p >= 1, außerdem teilt 2^(k_p) die Zahl \phi(a). Wegen \phi(a) = \Theta(a)^2 tritt der Primfaktor 2 genau einmal in a auf, d.h. es gilt:

Entweder hat a einen ungeraden Primfaktor p mit p == 5 (mod 8), oder a hat zwei ungerade Primfaktoren p und q mit p == q == 3 (mod 4)


Im ersten dieser beiden Fälle ist dann p-1 eine Zweierpotenz, und weil der Faktor 2 genau zweimal in \phi(a) vorkommt, gilt entweder p = 3 oder p = 5.
Im ersten Fall ergibt sich a = 2^2 * 3^3 = 108, 
im zweiten a = 2 * 5^3 = 250.

Den zweiten Teil hab ich noch nicht fertigüberlegt.

Im verbleibenden Fall muss die kleinere Primzahl q = 2^m + 1 sein, ansonsten schleppt man sich in \phi(a) einen zusätzlichen ungeraden Primfaktor ein.
Weiter folgt q = 2^1 + 1 = 3, denn sonst tritt der Primfaktor 2 in \Theta(a) mehr als zweimal auf.

Der Primfaktor q = 3 kann nun entweder einmal oder zweimal in a auftreten, ansonsten tritt der Primfaktor 3 in \Theta(a) mehr als zweimal auf.

Im ersten Fall erhält man
a = 2 * 3^2 * 7^3 = 6174,
im Zweiten Fall:
a = 2 * 3 * 19^3 = 41154

Insgesamt sind es also die 6 Lösungen:
1,8,108,250,6174,41154

Lösungsweg:

Gesucht sind alle Lösungen von
 \phi(m)=\theta(m)^2 mit \theta(1)=1.

Man sieht sofort dass m=1 eine Lösung ist. Nun gilt \phi(m)=m*produkt((1-1/p),p\|m,). Setzen wir dies ein so erhalten wir 
m*produkt((1-1/p),p\|m,)=produkt(p^2,p\|m,)
 bzw.
 m*produkt((p-1),p\|m,)=produkt(p^3,p\|m,)

Die linke Seite ist gerade, daher ist ein Primfaktor (o.B.d.A. p_1) gleich 2. Für jede ungerade Primzahl ist p-1 gerade und liefert einen Beitrag zur Zweierpotenz auf der rechten Seite. Es können daher maximal drei unterschiedliche Primfaktoren p_1, p_2 und p_3 sein.

1. Fall: ein Primfaktor

Wir haben bereits gesehen dass p_1=2 und daher:
m*(2-1)=2^3 => m=8

2. Fall: zwei Primfaktoren

m*(2-1)*(p_2-1)=2^3*p_2^3

Nun ist p_2-1 kein Teiler von p_2 weshalb p_2-1\|2^2 => p_2=3 oder p_2=5.

m*(2-1)*(3-1)=2^3*3^3 =>m=2^2*3^3=108
m*(2-1)*(5-1)=2^3*5^3 =>m=2*5^3=250

3. Fall: drei Primfaktoren

m*(2-1)*(p_2-1)*(p_3-1)=2^3*p_2^3*p_3^3

Aus der selben Argumentation wie oben folgt p_2=3 oder p_2=5.

Fall 3a) p_2=3

Es ist p_3-1 kein Teiler von p_3 und daher p_3-1\|2*3^3. Jene Teiler d von 2*3^3 für die d+1 prim ist ( und ungleich 3) führen auf p_3=7 und p_3=19.

m*(2-1)*(3-1)*(7-1)=2^3*3^3*7^3 =>m=2*3^2*7^3=6174
m*(2-1)*(3-1)*(19-1)=2^3*3^3*19^3 =>m=2*3*19^3=41154

Fall 3b) p_3=5

Es gibt keine Teiler d von 5^3 für die d+1 prim ist.