phi(n) teilt n - wann? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Bestimmen Sie alle positiven [mm]n \in \IN[/mm], für die [mm]\phi(n)[/mm] ein Teiler von n ist. |
Guten Tag!
Ich weiß, dass [mm]\phi(n) = n* \produkt_{i=1}^{r}( \bruch{p_i - 1}{p_i}\left)[/mm]
Ich vermute nun, dass das dann n teilt, wenn das Produkt, welches mit n multipliziert wird, wiederrum eine natürliche Zahl ist. Dazu müssten sich die ganzen Nenner wegkürzen. Ich denke dass dadurch, dass man von einer Primzahl 1 abzieht, das Resultat ein Produkt der vorangegangenen Primzahlen ist - nur enthält es dann auch zwangsweise ALLE vorangegangenen Primzahlen, sodass sie sich wegkürzen? Wenn ja, wie würde ich das zeigen - bzw herausfinden, bei welchen n's dies der Fall ist?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
viele Grüße,
Leon
|
|
| |
|
> Bestimmen Sie alle positiven [mm]n \in \IN[/mm], für die [mm]\phi(n)[/mm] ein
> Teiler von n ist.
Hallo,
Du schreibst es zwar nicht, aber ich vermute sehr stark, daß die [mm] p_i [/mm] die Primfaktoren von n sein sollen, also [mm] n=\produkt_{i=1}^{r}p_i^{m_i} [/mm] (Primfaktorzerlegung).
[mm] \phi [/mm] ist hier dann die Eulersche Phifunktion, welche die Anzahl der zu n teilerfremden Zahlen < n angibt.
> Ich weiß, dass [mm]\phi(n) = n* \produkt_{i=1}^{r}( \bruch{p_i - 1}{p_i})[/mm]
>
> Ich vermute nun, dass das dann n teilt, wenn das Produkt,
> welches mit n multipliziert wird, wiederrum eine natürliche
> Zahl ist.
Schauen wir uns diese Vermutung an:
was bedeutet es, wenn [mm] \phi(n) [/mm] Teiler von n ist?
In diesem Falle gibt es ein k [mm] \in \IN [/mm] so, daß
[mm] k*\phi(n)=n
[/mm]
<==>
k*n* [mm] \produkt_{i=1}^{r}( \bruch{p_i - 1}{p_i}) [/mm] = n
<==> (teilen durch n)
k* [mm] \produkt_{i=1}^{r}( \bruch{p_i - 1}{p_i}) [/mm] = 1
Spätestens dieser Stelle siehst Du jetzt, daß Du mit Deiner Vermutung nicht richtig lagst. Das "große" Produkt muß nicht eine natürliche Zahl sein, k kann das "auffangen". Es wäre sogar seltsam, wäre es eine natürliche Zahl: der Nenner ist ja größer als der Zähler!
Aber gehen wir einen Schritt weiter :
...
<==> k* [mm] \produkt_{i=1}^{r}(p_i [/mm] - 1) = [mm] \produkt_{i=1}^{r}p_i [/mm]
Gucken wir uns das genauer an. Rechts haben wir ein Produkt von r verschiedenen Primzahlen.
Von den [mm] (p_i [/mm] - 1) auf der rechten Seite werden sehr viele gerade sein...
Also ...
Hier verlasse ich Dich. Denk mal in diese Richtung weiter!
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:23 Mo 05.02.2007 | | Autor: | Fylosofus |
Okay, vielen Dank.
So etwas ähnliches hat auch schon irgendwo auf den Schmierzetteln gestanden, aber die Antwort gab dann den nötigen Anstoß in die richtige Richtung :)
Aufgabe (denke ich) richtig gelöst.
viele Grüße
|
|
|
|
