Phi-Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:48 So 14.11.2010 | | Autor: | Scharii |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe 1 | Es bezeichne $\phi$ die Eulersche $\phi$-Funktion und kgV($a,b$) das kleinste gemeinsame Vielfache zweier ganzer Zahlen $a,b$.
Es seien $a,b,n \in \IN$ mit $n=ab$ und ggT$(a,b)=1$.
Beweisen sie, dass dann für $m\in \IN$ mit ggt$(m,n)=1$ gilt dass
$m^{kgV(\phi(a),\phi(b))}\equiv 1$ (mod $n$) |
| Aufgabe 2 | Es sei wieder $\phi$ die Eulersche $\phi$-Funktion. Zeigen Sie, dass für beliebige natürliche Zahlen $n$ und $m$ die Gleichung $\phi(mn)=\frac{\phi(n)\phi(m)g}{\phi(g)}$ gilt, wobei $g=$ggT$(m,n)$
Zeigen Sie für alle natürlichen Zahlen $n$ die Identität $n=\sum_{d|n}{\phi(d)$. |
Hi, ich brauche Hilfe bei der Lösung der beiden Aufgaben bitte.
Zu 1:
Ich weiss dass wegen $ggT(a,b)=1$ gilt $kgV(a,b)=ab)$
Ansonsten fällt mir nur ein dass a und b keine gemeinsamen Primfaktoren haben, also die die ich bei $\phi(a)$ zähle zähle ich nicht bei $\phi(b)$ und umgekehrt, aber wie ich damit weiterkomme weiss ich nicht wirklich.
Zu 2: Ich habe versucht das ganze in Primzahlen zu zerlegen und dann auseinanderzurechnen...
Bin dann gekommen auf $\phi(mn)=\phi(p_1 \ldots p_{i-1})\phi(q_1 \ldots q_{j-1})\phi(p_i \ldots p_m q_j \ldots q_n)$ wobei der letzte Term die Primzahlen hat die sowohl in m als auch in n sind und die ersten beiden die die disjunkt sind.
Aus dem 3. Term müsst ich jetzt eben noch ableiten dass $\phi(p_i \ldots p_m q_j \ldots q_n)=\frac{g}{\phi(g)}
Ich hoffe das ist nicht zu verwirrend was ich schreibe und dass ihr mir helfen könnt,
Danke schonmal im voraus :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:27 Mo 15.11.2010 | | Autor: | wauwau |
1) Nach Euler ist
[mm] $m^{\varphi(a)} \equiv [/mm] 1(a)$ da [mm] $kgv(\varphi(a),\varphi(b))$ [/mm] ein Vielfaches von [mm] $\varphi(a)$ [/mm] ist daher
[mm] $m^{kgv(\varphi(a),\varphi(b))} \equiv [/mm] 1(a)$
Dieselbe Beziehung gilt für b daher folgt nach chin.Restsatz die Behauptung
2. aufgabe in meinem nächst. Post
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:47 Mo 15.11.2010 | | Autor: | wauwau |
2)
Die identität
[mm] \varphi(n)=n.\produkt_{}^{}(1-\frac{1}{p_i}) [/mm] wobei [mm] p_i [/mm] die Primfaktoren von n sind, kennst du!?
Dann seien die Primfaktoren von ggt(m,n) [mm] p_i
[/mm]
die von m dann [mm] p_i [/mm] und [mm] q_i
[/mm]
die von m dann [mm] p_i [/mm] und [mm] r_i
[/mm]
dann gilt
[mm] \varphi(m.n)=m.n.\produkt_{}^{}(1-\frac{1}{p_i})\produkt_{}^{}(1-\frac{1}{q_i})\produkt_{}^{}(1-\frac{1}{r_i})=m.\produkt_{}^{}(1-\frac{1}{p_i}).\produkt_{}^{}(1-\frac{1}{q_i}).n.\produkt_{}^{}(1-\frac{1}{p_i})\produkt_{}^{}(1-\frac{1}{r_i}).\frac{1}{\produkt_{}^{}(1-\frac{1}{p_i})}=\varphi(m)\varphi(n)\frac{1}{\produkt_{}^{}(1-\frac{1}{p_i})}
[/mm]
da
[mm] \varphi(ggt(m,n))=ggt(m,n).\produkt_{}^{}(1-\frac{1}{p_i})
[/mm]
folgt die Behauptung
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:07 So 28.11.2010 | | Autor: | Scharii |
Danke für die Hilfe, bin noch selbst auf die Lösung gekommen...
Aber gut sich bestätigt zu wissen :)
|
|
|
|
