Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Eulersche Phi-Funktion

Eulersche Phi-Funktion

Universität / Fachhochschule

Tags: phi-funktion, Zahlentheorie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Sukomaki

Sukomaki aktiv_icon

19:00 Uhr, 17.02.2020

Antworten
Hallo,

ich sitze gerade an einem Beweis einer Vermutung aus der Zahlentheorie.
Es geht dabei unter anderem um die eulersche φ-Funktion.

φ(n)=ggT(k,n)=11

φ2(n):=ggT(k,n)=1k

Daraus folgt (V1) :
n>1:φ2(n)=n2φ(n)

Seien n1,n2>1 relativ prim.

Dann ist φ2(n1n2)=n1n22φ(n1n2)=n1n22φ(n1)φ(n2)=2n12n22φ(n1)φ(n2)=2φ2(n1)φ2(n2)

Damit ist φ2 "quasi multiplikativ".

Jetzt möchte ich V1 beweisen.

Hat jemand eine Idee, wie das zu bewerkstelligen ist?

Sei M eine Teilmenge von {0,,n-1} aus r Elementen.

Dann seien :
s1(M):=M=r und s2(M):=i=1rmi

Mein Ansatz ist 2s2(M)=ns1(M)+a in Äquivalenzklassen An(a) zu zerlegen und dann
zu zeigen, dass gn:={m{1,,n}ggT(m,n)=1} in An(0) liegt.

Sei M:={m1,,mr}.

Dann muss i=1rmi=n2r sein.

Elemente von An(0) sind unter anderem :
{},
sn:={1,,n-1},
i={1,,n2}:{i,n-i},sn\{i,n-i}

Letzteres wegen snʹ:=sn\{i,n-i}s2(snʹ)=s2(sn)-n=n2(s1(sn)-2)=n2s1(snʹ).

Leider ist es mir nicht gelungen zu zeigen, warum gn in An(0) liegt.

Vielleicht klappt da ein total anderer Ansatz?

Gruß
Maki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Online-Nachhilfe in Mathematik
Antwort
HAL9000

HAL9000

07:43 Uhr, 18.02.2020

Antworten
Halten wir erstmal fest: Du summierst nicht über alle k mit ggT(k,n)=1, sondern nur über die mit 1kn, die das erfüllen, für n>1 genügt auch die Betrachtung 1kn-1. Bezeichnen wir die Menge dieser k mit M.

Jetzt kann man jedem kM eineindeutig die Zahl n-kM zuordnen, denn aus ggT(n,k)=1 folgt ggT(n,n-k)=1 und umgekehrt. Damit folgt

2φ2(n)=kMk+kMk=kMk+kM(n-k)=kMn=nφ(n) .


Sukomaki

Sukomaki aktiv_icon

10:29 Uhr, 19.02.2020

Antworten
Krass,

so einfach ist das? :-)

Aber warum ist ggT(n,k)=1ggT(n,n-k)=1?

Ich vermute es ist so :

ggT(n,k)=ggT(n,-k)=ggT(n,-k+1n)

Du hast natürlich recht, dass ich nur über 1kn summiere.
Das habe ich stillschweigend vorausgesetzt.


Antwort
HAL9000

HAL9000

11:11 Uhr, 19.02.2020

Antworten
Ja, das ist eine Möglichkeit, das mit dem ggT zu begründen.

Und: Ja, so einfach kann das sein, wenn man sich auf das Wesentliche konzentriert und sich nicht gleich im Klein-klein verliert. ;-)

Frage beantwortet
Sukomaki

Sukomaki aktiv_icon

13:23 Uhr, 19.02.2020

Antworten
Ok,

vielen Dank :-)