Multiplikativität der Phi-Fkt. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie, dass für natürliche Zahlen [mm] m_{1} [/mm] und [mm] m_{2} [/mm] mit [mm] ggT(m_{1},m_{2})=1 [/mm] gilt:
[mm] \phi{(m_{1}*m_{2})} [/mm] = [mm] \phi{m_{1}} [/mm] * [mm] \phi{m_{2}} [/mm] |
Hallo!
Ich habe mir aus einem Buch einen Beweis rausgesucht, den ich leider nicht so ganz verstehe:
Unter der Voraussetzung, dass [mm] m_{1} [/mm] und [mm] m_{2} [/mm] teilerfremde nat. Zahlen sind (d.h. [mm] ggT(m_{1},m_{2})=1), [/mm] durchläuft [mm] a_{2}*m_{1}+a_{1}*m_{2} [/mm] ein vollständiges Restsystem modulo [mm] m_{1}*m_{2}, [/mm] wenn [mm] a_{1} [/mm] und [mm] a_{2} [/mm] jeweils ein vollständiges Restsystem modulo [mm] m_{1} [/mm] bzw. [mm] m_{2} [/mm] durchlaufen.
Fragen: Wieso diese Formel [mm] a_{2}*m_{1}+a_{1}*m_{2}? [/mm] Und [mm] a_{1} [/mm] und [mm] a_{2} [/mm] stehen für Restklassen in [mm] Z/m_{1}Z [/mm] bzw. [mm] Z/m_{2}Z, [/mm] oder?
Es muss gelten [mm] ggT(a_{2}*m_{1}+a_{1}*m_{2},m_{1}*m_{2})=1.
[/mm]
Frage: Wieso muss das gelten?
Dies gilt genau dann, wenn [mm] ggT(a_{2}*m_{1}+a_{1}*m_{2},m_{1})=1 [/mm] und [mm] ggT(a_{2}*m_{1}+a_{1}*m_{2},m_{2})=1.
[/mm]
Dies ist genau dann der Fall, wenn die Beziehungen [mm] ggT(a_{1}*m_{2},m_{1})=1 [/mm] und [mm] ggT(a_{2}*m_{1},m_{2})=1 [/mm] gelten.
Dazu muss [mm] ggT(a_{1},m_{1})=1 [/mm] und [mm] ggT(a_{2},m_{2}) [/mm] sein.
Frage: Und wieso beweist das die Behauptung?
Ich hoffe es kann mir jemand helfen.
Danke schonmal.
Gruß,
Coffein18
|
|
| |
|
Hallo Coffein,
vorab:
Darfst Du für den Beweis schon eine Berechnungsformel für [mm] \varphi(n) [/mm] benutzen? Dann ist das schnell zu erledigen mit
[mm] \varphi(n)=\produkt_{p_i|n}p_i^{\alpha_i}\left(1-\bruch{1}{p_i}\right)=n*\produkt_{p_i|n}\left(1-\bruch{1}{p_i}\right)
[/mm]
wobei natürlich [mm] n=\produkt_{p_i|n}p_i^{\alpha_i} [/mm] vorausgesetzt ist.
> Beweisen Sie, dass für natürliche Zahlen [mm]m_{1}[/mm] und [mm]m_{2}[/mm]
> mit [mm]ggT(m_{1},m_{2})=1[/mm] gilt:
> [mm]\phi{(m_{1}*m_{2})}[/mm] = [mm]\phi{m_{1}}[/mm] * [mm]\phi{m_{2}}[/mm]
>
>
> Hallo!
> Ich habe mir aus einem Buch einen Beweis rausgesucht, den
> ich leider nicht so ganz verstehe:
>
> Unter der Voraussetzung, dass [mm]m_{1}[/mm] und [mm]m_{2}[/mm] teilerfremde
> nat. Zahlen sind (d.h. [mm]ggT(m_{1},m_{2})=1),[/mm] durchläuft
> [mm]a_{2}*m_{1}+a_{1}*m_{2}[/mm] ein vollständiges Restsystem
> modulo [mm]m_{1}*m_{2},[/mm] wenn [mm]a_{1}[/mm] und [mm]a_{2}[/mm] jeweils ein
> vollständiges Restsystem modulo [mm]m_{1}[/mm] bzw. [mm]m_{2}[/mm]
> durchlaufen.
>
> Fragen: Wieso diese Formel [mm]a_{2}*m_{1}+a_{1}*m_{2}?[/mm] Und
> [mm]a_{1}[/mm] und [mm]a_{2}[/mm] stehen für Restklassen in [mm]Z/m_{1}Z[/mm] bzw.
> [mm]Z/m_{2}Z,[/mm] oder?
Ja. Die Formel wird hier angesetzt, um die Zahl der zu [mm] m_1*m_2 [/mm] teilerfremden Restklassen zu bestimmen.
> Es muss gelten [mm]ggT(a_{2}*m_{1}+a_{1}*m_{2},m_{1}*m_{2})=1.[/mm]
>
> Frage: Wieso muss das gelten?
Das wird mit den folgenden Beziehungen erst hergeleitet bzw. begründet.
> Dies gilt genau dann, wenn
> [mm]ggT(a_{2}*m_{1}+a_{1}*m_{2},m_{1})=1[/mm] und
> [mm]ggT(a_{2}*m_{1}+a_{1}*m_{2},m_{2})=1.[/mm]
> Dies ist genau dann der Fall, wenn die Beziehungen
> [mm]ggT(a_{1}*m_{2},m_{1})=1[/mm] und [mm]ggT(a_{2}*m_{1},m_{2})=1[/mm]
> gelten.
> Dazu muss [mm]ggT(a_{1},m_{1})=1[/mm] und [mm]ggT(a_{2},m_{2})[/mm] sein.
>
> Frage: Und wieso beweist das die Behauptung?
Das ist eine gute Frage. Ohne Verwendung des chin.Restsatzes und des Lemmas von Bézout zeigt das nur, dass [mm] \ggT{(a_2m_1+a_1m_2,m_1m_2)}=1\gdw\ggT{(a_1,m_1)}=\ggT{(a_2,m_2)}=1.
[/mm]
> Ich hoffe es kann mir jemand helfen.
> Danke schonmal.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:30 Mi 22.05.2013 | | Autor: | reverend |
Hallo nochmal,
![[]](/images/popup.gif) hier steht ein kurzer, nachvollziehbarer Beweis, ab "5.3. Satz", S.1 unten. Der eigentliche Beweis dann S.2 oben.
Grüße
reverend
|
|
|
| |
|
Hallo!
Mir ist aufgefallen, dass der Beweis auf der nächsten Seite noch weiter ging. Dort steht sozusagen noch das Ende des Beweises und wohl die Erklärung dafür, dass der Beweis das Behauptete beweist:
Damit sind die [mm] \phi{(m_{1}*m_{2})} [/mm] zu [mm] m_{1}*m_{2} [/mm] teilerfremden Zahlen unterhalb [mm] m_{1}*m_{2} [/mm] die kleinsten positiven Reste der [mm] \phi{m_{1}}*\phi{m_{2}} [/mm] Zahlen [mm] a_{2}*m_{1}+a_{1}*m_{2} [/mm] mit [mm] ggT(a_{1},m_{1})=1 [/mm] und [mm] ggT(a_{2},m_{2})=1. [/mm] Damit ist unsere Behauptung bewiesen.
Kann mir vielleicht jemand den Satz etwas verständiglicher erklären?
Danke & viele Grüße,
Coffein18
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Sa 25.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Fr 24.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
