eulerphi mit inklusion/ex. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei $n [mm] \in \IN$, [/mm] n>1 und [mm] $n=p_1^{a_1}*p_2^{a_2}*\cdots [/mm] * [mm] p_k^{a_k}$ [/mm] die Primfaktorzerlegung von $n$ (die [mm] $p_i$ [/mm] also paarweise verschieden und alles was dazugehört).
Man zeige mit Hilfe des Inklusions-Exklusionsprinzips:
[mm] $|E(\IZ/n\IZ)| [/mm] = [mm] n\prod_{i=1}^k (1-p_i^{-1})$ [/mm] |
moin,
Bei obiger Aufgabe habe ich grad so meine Probleme.
Der Beweis der Identität ist nicht weiter schwierig, wenn ich Wissen aus der Zahlentheorie voraussetzen dürfte.
Allerdings stammt diese Aufgabe aus einer Anfängervorlesung und die Phifunktion ist hier noch nicht bekannt.
Das einzige, was für den Beweis benutzt werden darf, ist die Tatsache, dass
[mm] $|E(\IZ/n\IZ)| [/mm] = | [mm] \{ k \in \IN : 1 \leq k \leq n, ggT(k,n)=1 \} [/mm] |$.
Inklusions-Exklusions-technisch wollte ich es versuchen mit:
[mm] $\IZ_n$ [/mm] hat $n$ Elemente.
Davon sind [mm] $\left[ \frac{n}{p_1} \right]$ [/mm] durch [mm] $p_1$ [/mm] teilbar, etc.
Das bringt mich allerdings nur auf eine große Summe, aber bei weitem nicht auf das gewünschte Produkt.
Wenn jemand einen feinen Weg sieht, wie man die Aussage einzig mit "logischen Überlegungen" und ohne zahlentheoretisches Vorwissen lösen kann wäre das echt praktisch.
thx schonmal
lg
Schadow
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:03 Mo 30.01.2012 | | Autor: | felixf |
Moin Schadow!
> Sei [mm]n \in \IN[/mm], n>1 und [mm]n=p_1^{a_1}*p_2^{a_2}*\cdots * p_k^{a_k}[/mm]
> die Primfaktorzerlegung von [mm]n[/mm] (die [mm]p_i[/mm] also paarweise
> verschieden und alles was dazugehört).
> Man zeige mit Hilfe des Inklusions-Exklusionsprinzips:
> [mm]|E(\IZ/n\IZ)| = n\prod_{i=1}^k (1-p_i^{-1})[/mm]
> moin,
>
> Bei obiger Aufgabe habe ich grad so meine Probleme.
> Der Beweis der Identität ist nicht weiter schwierig, wenn
> ich Wissen aus der Zahlentheorie voraussetzen dürfte.
> Allerdings stammt diese Aufgabe aus einer
> Anfängervorlesung und die Phifunktion ist hier noch nicht
> bekannt.
> Das einzige, was für den Beweis benutzt werden darf, ist
> die Tatsache, dass
> [mm]|E(\IZ/n\IZ)| = | \{ k \in \IN : 1 \leq k \leq n, ggT(k,n)=1 \} |[/mm].
>
> Inklusions-Exklusions-technisch wollte ich es versuchen
> mit:
> [mm]\IZ_n[/mm] hat [mm]n[/mm] Elemente.
> Davon sind [mm]\left[ \frac{n}{p_1} \right][/mm] durch [mm]p_1[/mm] teilbar,
> etc.
Genau. So wuerde ich damit anfangen.
Sei [mm] $A_{i_1, \dots, i_k}$ [/mm] die Anzahl der Restklassen $x + [mm] n\IZ$ [/mm] mit $0 [mm] \le [/mm] x < n$ und [mm] $p_{i_1}, \dots, p_{i_k} \mid [/mm] x$.
Dann ist $n - [mm] |E(\IZ/n\IZ)| [/mm] = [mm] \sum_{m=1}^k \underset{1 \le i_1 < \dots < i_m \le n}{\sum\cdots\sum} (-1)^{m-1} A_{i_1, \dots, i_k}$. [/mm] Jetzt ist [mm] $A_{i_1, \dots, i_k} [/mm] = [mm] \frac{n}{p_{i_1} \cdots p_{i_k}}$, [/mm] womit also [mm] $|E(\IZ/n\IZ)| [/mm] = n + [mm] \sum_{m=1}^k \underset{1 \le i_1 < \dots < i_m \le n}{\sum\cdots\sum} (-1)^m \frac{n}{p_{i_1} \cdots p_{i_m}}$ [/mm] ist.
Das kannst du jetzt schreiben als $n [mm] \sum_{e_1=0}^1 \cdots \sum_{e_k=0}^1 (-1)^{e_1 + \cdots + e_k} \frac{1}{p_1^{e_1} \cdots p_k^{e_k}}$.
[/mm]
Das kannst du jetzt mit dem Distributivgesetz schreiben als $n [mm] \cdot \prod_{i=1}^k [/mm] (...)$, und das in den Klammern sollte sich wie gewuenscht vereinfachen.
LG Felix
|
|
|
|
