Endliche Zahl von m für phi(m) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:26 Fr 01.07.2011 | | Autor: | clemenum |
| Aufgabe | Eulerphi-Funktion:
Man zeige:
Zu jedem [mm] $n\in \mathbb{N}$ [/mm] gibt es nur endlich viele [mm] $m\in \mathbb{N},$ [/mm] sodass [mm] $\varphi(n) [/mm] = m$ |
Also, mit anderen Worten ist doch zu zeigen, dass, wenn ich ein beliebiges Bildelement nehme, es zu diesem nur endlich viele Urbildelemente gibt.
Also, konkrete gesproochen - so fasse ich dies zumindest auf - geht es um darum zu zeigen, dass nicht so etwas wie:
[mm] $\varphi(45)=m, \varphi(47) [/mm] =m, [mm] \varphi(49)=m, \ldots [/mm] $ gelten kann.
Meine Überlung ist nun, dass ich mir die Primfaktorzerlegung von $m$ ansehen, etwa: [mm] $m=\prod_{j}{p_j}^{\alpha_j}$ [/mm] und mir alle teilerfremden Zahlen bis zu m anschaue und irgendwie nachweise, dass es in jedem Fall nur eine endliche Anzahl geben kann. Das scheint aber sehr schwierig zu sein. Wie soll man das denn "ablesen" können??
Ich würde mich über Hilfe freuen!
|
|
| |
|
Hallo clemenum,
das ist aber eine ganz andere Aufgabe. Ich mache gleich mal einen eigenen Thread daraus.
Es ist besser, Du schaust Dir die kanonische Zerlegung von [mm] \varphi(m) [/mm] an und überlegst, wie man daraus die möglichen m rekonstruieren kann. Dann bist Du schnell an der Stelle, wo man die Endlichkeit leicht zeigen kann.
Grüße
reverend
PS: Was besagt z.B. ein ungerader Faktor (also eine Primzahl>2) in der Zerlegung von [mm] \varphi(m) [/mm] ?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:42 Fr 01.07.2011 | | Autor: | clemenum |
Hallo Reverend!
Erstmal, danke ich dir für deine rasche Antwort! 
Ich finde das Beispiel ein wenig verwirrend. Machen wir dazu doch - der besseren Verständlichkeit halber - ein konkretes Beispiel:
Du meinst also, ich soll mir überlegen, wie man etwa aus [mm] $\varphi(m) [/mm] = 20 $ auf die Anzahl der $m$ für die [mm] $\varphi(m) [/mm] = 15 $ gilt, rückschließen kann?
Und du meinst, das erkenne ich aus der Zerlegung $15=3 [mm] \cdot [/mm] 5 $ ?
Meinst du vielleicht, dass ich hier wieder die Multiplikativität der Euler-Phi Funktion benutzen soll (denn in der kanonischen Zerlegung sind ja alle Faktoren (bis auf Vielfachheit) paarweise teilerfremd).
Vielleicht auf die Weise:
[mm] $\varphi(15) [/mm] = [mm] \varphi(3) \cdot \varphi(5) [/mm] $ ?
Ich wäre dir sehr dankbar, wenn du mir dies für dieses konkrete Beispiel vorexazierst!
|
|
|
| |
|
Hallo clemenum,
so ganz trivial ist die Aufgabe nicht, aber schwierig ist sie auch nicht.
> Ich finde das Beispiel ein wenig verwirrend. Machen wir
> dazu doch - der besseren Verständlichkeit halber - ein
> konkretes Beispiel:
Ok.
> Du meinst also, ich soll mir überlegen, wie man etwa aus
> [mm]\varphi(m) = 20[/mm] auf die Anzahl der [mm]m[/mm] für die [mm]\varphi(m) = 20[/mm]
> gilt, rückschließen kann?
> Und du meinst, das erkenne ich aus der Zerlegung
> [mm]20=2^2\cdot 5[/mm] ?
Nicht direkt, siehe unten.
> Meinst du vielleicht, dass ich hier wieder die
> Multiplikativität der Euler-Phi Funktion benutzen soll
> (denn in der kanonischen Zerlegung sind ja alle Faktoren
> paarweise teilerfremd).
> Vielleicht auf die Weise:
> [mm]\varphi(20) = \varphi(2) \cdot \varphi(2) \cdot \varphi(5)[/mm]
Na, das klappt so nicht. Außerdem sind die beiden Zweien ja nicht teilerfremd zueinander.
> Ich wäre dir sehr dankbar, wenn du mir dies für dieses
> konkrete Beispiel vorexazierst!
Also gegeben [mm] \varphi(m)=20=2^2*5
[/mm]
Die 5 stammt entweder daher, dass [mm] 5^k|m [/mm] mit k>1. Dann muss aber auch (5-1) ein Faktor von [mm] \varphi(m) [/mm] sein. Siehe da, das klappt. Wir haben ein mögliches m:
[mm] m_1=5^2, \varphi{m_1}=20
[/mm]
Weitere m, die den Faktor 5 beinhalten, kann es nicht geben.
Dann kann die 5 also noch daher kommen, dass ein (p-1) durch 5 teilbar ist. Da aber für p>2 alle p-1 gerade sind, kommen für p-1 nur 2 Möglichkeiten in Frage:
p-1=2*5, also p=11, und wir haben noch eine 2 übrig, die kann nur aus (3-1) entstanden sein.
Daher [mm] m_2=3*11, \varphi{m_2}=20
[/mm]
Und schließlich bleibt noch [mm] p-1=5*2^2, [/mm] aber leider ist 21 nicht prim.
Es scheint, wir wären fertig, aber da gibt es noch eine Hinterlistigkeit. Es ist ja [mm] \phi(2)=1, [/mm] und solange unsere m ungerade sind, dürfen wir also noch eine 2 dranmultiplizieren, ohne dass sich [mm] \varphi [/mm] ändert. (Anders, wenn die 2 bereits vorkommt - überleg das mal selbst!)
Also gibt es noch
[mm] m_3=2*5^2 [/mm] und [mm] m_4=2*3*11 [/mm] mit [mm] \varphi(m_3)=\varphi(m_4)=20
[/mm]
***
Nun kann dieser Weg schon etwas mühsam werden, wenn die Zerlegung mehr Faktoren enthält. Aber es ging doch nur darum, die Endlichkeit zu zeigen.
Da [mm] \varphi(m) [/mm] eine endliche Zahl ist, somit auch eine endliche Zerlegung hat, ist nur noch zu zeigen, dass diese nur aus endlich vielen m herrühren kann. Das ist aber wirklich fast trivial. - Achtung: es geht ja gar nicht darum, dass Du zeigst, wie man rekonstruiert, aber zu jeder "Gruppierung" der Faktoren von [mm] \varphi(m) [/mm] gibt es höchstens eine endliche Zahl von m (normalerweise nur ein oder zwei; konstruier mal was anderes...), und da die Zahl der möglichen "Gruppierungen" auch endlich ist, ist also die Gesamtzahl aller möglichen m ebenfalls endlich.
Soweit der Prosatext. 
Grüße
reverend
|
|
|
| |
|
> so ganz trivial ist die Aufgabe nicht
Hallo reverend ,
so wie die Aufgabe gestellt ist, nämlich:
Zu jedem [mm] $\red{n\in \mathbb{N}}$ [/mm] gibt es nur endlich viele [mm] $\red{m\in \mathbb{N}}, [/mm] $ sodass [mm] $\red{\varphi(n) = m}$
[/mm]
ist sie nun wirklich trivial, denn die Funktion [mm] \varphi [/mm] ordnet
jedem [mm] n\in\IN [/mm] genau eine Zahl m mit [mm] m=\varphi(n) [/mm] zu ...
Vermutlich war aber folgende Aufgabe gemeint:
Zu jedem [mm] $\blue{ n\in \mathbb{N}} [/mm] $ gibt es nur endlich viele [mm] $\blue{ m\in \mathbb{N}}, [/mm] $ sodass [mm] $\blue{\varphi(m)=n} [/mm] $
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:36 Fr 01.07.2011 | | Autor: | reverend |
Oops.
Es ist nicht mein Tag für "close reading", wie es scheint.
Man liest sich halt die Aufgaben so zurecht, dass sie sinnvoll werden.
Grüße
rev
|
|
|
| |
|
> Eulerphi-Funktion:
> Man zeige:
> Zu jedem [mm]n\in \mathbb{N}[/mm] gibt es nur endlich viele [mm]m\in \mathbb{N},[/mm]
> sodass [mm]\varphi(n) = m[/mm]
>
> Also, mit anderen Worten ist doch zu zeigen, dass, wenn ich
> ein beliebiges Bildelement nehme, es zu diesem nur endlich
> viele Urbildelemente gibt.
>
> Also, konkrete gesproochen - so fasse ich dies zumindest
> auf - geht es um darum zu zeigen, dass nicht so etwas wie:
> [mm]\varphi(45)=m, \varphi(47) =m, \varphi(49)=m, \ldots[/mm] gelten
> kann.
>
> Meine Überlung ist nun, dass ich mir die
> Primfaktorzerlegung von [mm]m[/mm] ansehen, etwa:
> [mm]m=\prod_{j}{p_j}^{\alpha_j}[/mm] und mir alle teilerfremden
> Zahlen bis zu m anschaue und irgendwie nachweise, dass es
> in jedem Fall nur eine endliche Anzahl geben kann. Das
> scheint aber sehr schwierig zu sein. Wie soll man das denn
> "ablesen" können??
>
> Ich würde mich über Hilfe freuen!
Hallo clemenum,
bist du dir sicher, die Aufgabenstellung korrekt wiedergegeben
zu haben ?
Falls die Aufgabe wirklich so gestellt wurde, dann ist sie
eigentlich trivial !
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:31 Fr 01.07.2011 | | Autor: | felixf |
Moin!
Es reicht aus zu zeigen, dass [mm] $\varphi(n) \ge [/mm] f(n)$ ist fuer eine einfache Funktion $f$, fuer die du [mm] $\lim_{n\to\infty} [/mm] f(n) = [mm] \infty$ [/mm] zeigen kannst.
Dazu schau dir mal $n = [mm] \prod_{i=1}^k p_i^{e_i}$ [/mm] an. Dann ist [mm] $\varphi(n) [/mm] = n [mm] \cdot \prod_{i=1}^k \frac{p_i - 1}{p_i}$.
[/mm]
Da [mm] $p_i \ge [/mm] 2$ gilt [mm] $\frac{p_i - 1}{p_i} \ge \tfrac{1}{2}$, [/mm] fuer [mm] $p_i \ge [/mm] 3$ sogar [mm] $\frac{p_i - 1}{p_i} \ge \tfrac{2}{3}$. [/mm] Du hast also [mm] $\varphi(n) \ge [/mm] n [mm] \tfrac{1}{2} \cdot \cdot (2/3)^{k - 1}$.
[/mm]
Wieviele Primteiler $k$ kann $n$ hoechstens haben? Wenn du das einbaust, bist du schnell fertig.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:37 Sa 02.07.2011 | | Autor: | clemenum |
Ich danke euch allen, Reverend, Felixf, AlChwarizmi für eure Hilfe!
Durch die Vielfalt eurer Ansätze hab ich echt einiges dazugelernt!
|
|
|
|
