Beweis.\phi Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:51 Fr 18.05.2012 | | Autor: | sissile |
| Aufgabe | | Beweise: Zu jedem ungeraden m [mm] \in \IN [/mm] gibt es ein n [mm] \in \IN [/mm] mit [mm] n\not=m [/mm] und [mm] \phi(n)=\phi(m). [/mm] |
m= 2k +1 (k [mm] \in \IZ)
[/mm]
ZZ.: [mm] \exists [/mm] n: n [mm] \not= [/mm] m und [mm] \phi(n)=\phi(2k+1)
[/mm]
Ich weiß hier leider nicht, wie ich beginnen soll. Hat wer einen Tipp/Rat, was mir hier helfen könnte?
[mm] \phi(m) [/mm] = [mm] |\{k\in \IZ|0<=k<=m-1, ggtT(k,m)=1\}|
[/mm]
|
|
| |
|
Hallo sissile,
das ist eine leichte Aufgabe.
> Beweise: Zu jedem ungeraden m [mm]\in \IN[/mm] gibt es ein n [mm]\in \IN[/mm]
> mit [mm]n\not=m[/mm] und [mm]\phi(n)=\phi(m).[/mm]
> m= 2k +1 (k [mm]\in \IZ)[/mm]
> ZZ.: [mm]\exists[/mm] n: n [mm]\not=[/mm] m und
> [mm]\phi(n)=\phi(2k+1)[/mm]
>
> Ich weiß hier leider nicht, wie ich beginnen soll. Hat wer
> einen Tipp/Rat, was mir hier helfen könnte?
> [mm]\phi(m)[/mm] = [mm]|\{k\in \IZ|0<=k<=m-1, ggtT(k,m)=1\}|[/mm]
Was weißt Du über die Multiplikativität der [mm] \phi-Funktion?
[/mm]
Wenn [mm] \ggT(q,n)=1, [/mm] was kann man dann über [mm] \phi(q*n) [/mm] sagen?
Kennst Du diese Darstellung der [mm] \phi-Funktion:
[/mm]
[mm] \phi(n)=n*\produkt_{p|n}\left(1-\bruch{1}{p}\right)
[/mm]
Wenn das gesuchte n nun gerade wäre, was hieße das für [mm] \phi(n) [/mm] und den Exponenten des Primfaktors 2 ?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:25 Fr 18.05.2012 | | Autor: | sissile |
> Hallo sissile,
>
> das ist eine leichte Aufgabe.
schön
> > Beweise: Zu jedem ungeraden m [mm]\in \IN[/mm] gibt es ein n [mm]\in \IN[/mm]
> > mit [mm]n\not=m[/mm] und [mm]\phi(n)=\phi(m).[/mm]
> > m= 2k +1 (k [mm]\in \IZ)[/mm]
> > ZZ.: [mm]\exists[/mm] n: n [mm]\not=[/mm] m und
> > [mm]\phi(n)=\phi(2k+1)[/mm]
> >
> > Ich weiß hier leider nicht, wie ich beginnen soll. Hat wer
> > einen Tipp/Rat, was mir hier helfen könnte?
> > [mm]\phi(m)[/mm] = [mm]|\{k\in \IZ|0<=k<=m-1, ggtT(k,m)=1\}|[/mm]
>
> Was weißt Du über die Multiplikativität der
> [mm]\phi-Funktion?[/mm]
> Wenn [mm]\ggT(q,n)=1,[/mm] was kann man dann über [mm]\phi(q*n)[/mm]
> sagen?
[mm] \phi(qn) [/mm] = [mm] \phi(q)*\phi(n)
[/mm]
> Kennst Du diese Darstellung der [mm]\phi-Funktion:[/mm]
> [mm]\phi(n)=n*\produkt_{p|n}\left(1-\bruch{1}{p}\right)[/mm]
jap
> Wenn das gesuchte n nun gerade wäre, was hieße das für
> [mm]\phi(n)[/mm] und den Exponenten des Primfaktors 2 ?
wegen der oben gennanten darstellung wäre [mm] \phi(n) [/mm] ebenfalls gerade.
Das der Exponent nicht 0 ist?
|
|
|
| |
|
Hallo nochmal,
> > > Beweise: Zu jedem ungeraden m [mm]\in \IN[/mm] gibt es ein n
> [mm]\in \IN[/mm]
> > > mit [mm]n\not=m[/mm] und [mm]\phi(n)=\phi(m).[/mm]
> > > m= 2k +1 (k [mm]\in \IZ)[/mm]
> > > ZZ.: [mm]\exists[/mm] n: n [mm]\not=[/mm]
> m und
> > > [mm]\phi(n)=\phi(2k+1)[/mm]
> > >
> > > Ich weiß hier leider nicht, wie ich beginnen soll. Hat wer
> > > einen Tipp/Rat, was mir hier helfen könnte?
> > > [mm]\phi(m)[/mm] = [mm]|\{k\in \IZ|0<=k<=m-1, ggtT(k,m)=1\}|[/mm]
> >
> > Was weißt Du über die Multiplikativität der
> > [mm]\phi-Funktion?[/mm]
> > Wenn [mm]\ggT(q,n)=1,[/mm] was kann man dann über [mm]\phi(q*n)[/mm]
> > sagen?
> [mm]\phi(qn)[/mm] = [mm]\phi(q)*\phi(n)[/mm]
So ist es. Wenn nun q ungerade ist (also den Faktor 2 nicht enthält), n aber eine Zweierpotenz...
> > Kennst Du diese Darstellung der [mm]\phi-Funktion:[/mm]
> > [mm]\phi(n)=n*\produkt_{p|n}\left(1-\bruch{1}{p}\right)[/mm]
> jap
> > Wenn das gesuchte n nun gerade wäre, was hieße das für
> > [mm]\phi(n)[/mm] und den Exponenten des Primfaktors 2 ?
> wegen der oben gennanten darstellung wäre [mm]\phi(n)[/mm]
> ebenfalls gerade.
Schon. Aber finde doch mal alle Zahlen u, für die [mm] \phi(u) [/mm] ungerade ist. 
> Das der Exponent nicht 0 ist?
Natürlich nicht. Aber kann er >1 sein? Wenn ja, wie? Wenn nein, warum nicht?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:42 Fr 18.05.2012 | | Autor: | sissile |
Könntest du mir vlt vorher sagen, wechen Beweis du im Hinterkopf hast?
Ein Widerpruchsbeweis? Oder möchtest du das vorher für gerade n zeige und dannach für ungerade n?
Weil so muss ich dir sagen, komme ich nicht weiter.
Da m gerade(es enthält eine zweierpotenz) ist, ist ebenfall [mm] \phi(m) [/mm] gerade, also auch [mm] \phi(n)=> [/mm] n gerade
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:01 Fr 18.05.2012 | | Autor: | hippias |
Worauf reverend ganz bestimmt hinaus moechte: Multipliziere $m$ geschickt mit einer teilerfremdem Zahl $q$, sodass [mm] $\phi(qm)= \phi(m)$ [/mm] ergibt. Aufgrund der Multiplikativitaet und der Voraussetzung bietet sich dafuer eine Zahl ganz besonders an.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:11 Fr 18.05.2012 | | Autor: | sissile |
Hallo,
dann hat aber reverend die Rolle von m und n vertauscht?
m=2k +1, k [mm] \in \IZ
[/mm]
[mm] \phi(2k+1)= \phi(q*(2k+1))
[/mm]
dazu muss gelten ggt(2k+1,q)=1 und [mm] \phi(q)=1
[/mm]
ah und wenn ich q als 2 wähle erfüllt das die zwei kriterien und der beweis ist fertig?
LG
|
|
|
| |
|
Wenn man die Existenz von einem solchen n beweisen soll, dann genügt es dieses n anzugeben.
Es geht hier um die Tatsache, dass [mm]\phi(m)=\phi(2*m)[/mm] für m ungerade gilt. Vielleicht wäre es auch leichter zu sehen gewesen, wenn man für [mm]m\in\IN[/mm] die Primfaktorzerlegung lauter ungerader Primfaktoren hat
[mm]m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}[/mm]
und auf folgende Weise das [mm]\varphi[/mm] berechnet:
[mm]\varphi(m)=(p_1)^{a_1-1}(p_1-1)(p_2)^{a_2-1}(p_2-1)\cdots (p_r)^{a_r-1}(p_r-1)=\produkt_{i=1}^{r} \left ( p_i^{a_i-1}(p_i-1) \right )[/mm]
Dann ist [mm]\varphi(n)=\varphi(2m)=(2-1)^{1-1}(2-1)\varphi(m)[/mm]. Und das hast du auch heraus bekommen.
Ich wüsste im Moment auch nicht, warum hier noch auf den 2er Potenzen "herumgeritten" wird. Laut Aufgabe ist m ungerade. Das mit der Multiplikativität [mm] $\varphi(ab)=\varphi(a)\varphi(b)$ [/mm] war ja bekannt für teilerfremde a,b. Man hätte sich nur ein a teilfremd zu ungeraden Zahlen b überlegen müssen mit [mm] $\varphi(a)=1$. [/mm] Und da kommt man recht schnell auch a=2.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:00 Fr 18.05.2012 | | Autor: | sissile |
danke an euch 3.
LG
|
|
|
|
