Eulersche Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Aufgabe | Es sei n [mm] \in \IN. [/mm] Zeige:
a) Ist n keine Primzahl, so ist [mm] \phi(n)\le [/mm] n-2
b) Es gibt eine Zahl [mm] n\in \IN [/mm] mit [mm] \phi(n)=n-2
[/mm]
c) Ist [mm] n\not= [/mm] 1,2, so ist [mm] \phi(n) \ge [/mm] 2
d) Ist n ungerade, so ist [mm] \phi(8n)=4\phi(n)
[/mm]
[mm] (\phi [/mm] = Eulersche Funktion) |
Hi,
bei dieser Aufgabe habe ich leider bisher nur die d) hinbekommen. Und dies mit Hilfe der Multiplikavität.
Bei den anderen komme ich irgendwie werde nich voran. Könnt ihr mir da vielleicht weiterhelfen?
Grüße
|
|
|
|
Das kann man eigendlich recht schnell mit der inhaltlichen Definition der eulerschen Funktion zeigen:
http://de.wikipedia.org/wiki/Eulersche_%CF%86-Funktion
Bei a) sollst du zeigen, dass es (wenn n keine Primzahl ist) höchstens n-2 natürliche Zahlen geben kann, die zu n teilerfremd sind.
Das dürfte eigendlich klar sein; falls nicht überleg dir mal ein paar Beispiele, dann siehst du recht schnell wieso.
Bei b) musst du einfach so ein n finden. Als Tipp: Probier die ersten 10 Zahlen durch, da ist sicher eins dabei. ;)
Bei c) weißt du, dass jede natürliche Zahl größer 2 (die du hier betrachtest) auf jeden Fall teilerfremd zur 1 ist.
Du musst einzig eine zweite Zahl nennen, zu der diese Zahl ebenfalls teilerfremd ist (diese zweite Zahl kann man in Abhängigkeit von n eindeutig nennen).
Auch hier helfen, falls du keine findest, ein paar Beispiele weiter.
Die d) hast du ja schon ganz richtig gelöst. ;)
Also, benutze das Wissen, was genau [mm]\varphi(n)[/mm] bedeutet/wofür es steht, dann sollten diese Aufgaben kein Problem sein.
|
|
|
|
|
Also die b) habe ich jetzt auch, für n=4 gilt die Behauptung.
Aber bleiben wir mal bei a), denn die habe ich noch nicht hinbekommen.
Habe das mal für paar Zahlen ausprobiert.
[mm] \phi(6)=2 \le [/mm] 4
[mm] \phi(8)=4 \le [/mm] 6
[mm] \phi(10)=4 \le [/mm] 8
[mm] \phi(12)=4 \le [/mm] 10
Ich sehe aber gerade noch nciht, wie ich das auf ein bel. n [mm] \in \IN [/mm] schließen kann, wenn n keine Primzahl ist??
|
|
|
|
|
Du brauchst eine Zahl, die auf jeden Fall teilerfremd zu n ist.
Überleg mal:
3 ist teilfremd zu 2 und zu 1
4 ist teilerfremd zu 3 und zu 1
5 ist teilerfremd zu 4, zu 3, zu 2 und zu 1
6 ist teilerfremd zu 5 und zu 1
7 ist teierfremd zu 6,5,4,3,2 und 1
8 ist teilerfremd zu 7,5,3 und 1
erkennst du ein Muster?^^
|
|
|
|
|
hmmm,
entweder ist es schon zu spät, oder...
irgendwie erkenne ich kein muster, außer, dass bei den primzahlen gilt:
[mm] \phi(p)=p-1
[/mm]
Was soll denn da für ein muster dahinter stekcken? :-/
|
|
|
|
|
Ja, scheinbar ist es schon spät^^
Überleg mal, wieso für n>2 gilt: n und (n-1) sind teilerfremd.
(zB (2,3) sind teilerfremd, (3,4),(4,5),(5,6),(6,7),... sind alle jeweils teilerfremd)
|
|
|
|