Restklasse und Prim < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:09 So 24.02.2019 | | Autor: | magics |
| Aufgabe | Gegeben ist die Funktion [mm] $\Phi: \IN \to \IN \; [/mm] mit [mm] \; \Phi(n) [/mm] := [mm] |\{a | 1 \le a \le n \; und \; ggT(a,n) = 1\}|$
[/mm]
Sei nun $k [mm] \ge [/mm] 1$ und $p [mm] \; [/mm] prim$. Dann ist zu zeigen, dass: [mm] $\Phi(p^k) [/mm] = [mm] p^{k-1}(p-1)$ [/mm] |
Hallo,
scheinbar lautet der Lösungsweg [mm] $\red{\Phi(p^k)=p^k-\bruch{p^k}{p}}=p^k-p^k*p^{-1}=p^{k-1+1}-p^{k-1}=p^{k-1}*p-p^{k-1}*1=p^{k-1}(p-1)$
[/mm]
Ich verstehe die Umformung [mm] $\red{\Phi(p^k)=p^k-\bruch{p^k}{p}}$ [/mm] nicht. Man geht hier von folgendem aus:
[mm] $p^k$ [/mm] ist die Menge aller Elemente mit $1 [mm] \le [/mm] a [mm] \le [/mm] n$.
[mm] $\bruch{p^k}{p}$ [/mm] ist die Menge aller Elemente mit $ggT(a, [mm] p^k) \not= [/mm] 1$.
Wieso ist letzteres so?
Gibt es dazu einen Satz oder kann man das mit einem scharfen Auge sehen?
Grüße
Thomas
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:58 So 24.02.2019 | | Autor: | Fulla |
> [mm]p^k[/mm] ist die Menge aller Elemente mit [mm]1 \le a \le n[/mm].
>
> [mm]\bruch{p^k}{p}[/mm] ist die Menge aller Elemente mit [mm]ggT(a, p^k) \not= 1[/mm].
>
> Wieso ist letzteres so?
>
> Gibt es dazu einen Satz oder kann man das mit einem
> scharfen Auge sehen?
Hallo Thomas,
scharfes Hinsehen reicht hier aus:
Von den [mm]p^k[/mm] Zahlen ist jede [mm]p[/mm]-te Zahl durch [mm]p[/mm] teilbar, also nicht teilerfremd zu [mm]p^k[/mm]. Das sind [mm]\frac{p^k}{p}[/mm] Stück. (Das sind alle Zahlen [mm]\le p^k[/mm] mit gemeinsamen Teilern, da [mm]p^k[/mm] als einzigen Primfaktor [mm]p[/mm] hat.)
Beispiel: [mm]p=k=3[/mm]
Von den [mm]p^k=3^3=27[/mm] Zahlen ist jede dritte durch 3 teilbar, nämlich 3, 6, 9, 12, 15, 18, 21, 24 und 27. Das sind [mm]9=\frac{27}{3}=\frac{3^3}{3}[/mm] Stück.
Also ist [mm]\Phi(3^3)=27-9=18[/mm].
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 So 24.02.2019 | | Autor: | magics |
Merci für die Erklärung! Leuchtet mir ein :)
|
|
|
|
