Restsystem, Eulersche \phi F. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:21 Mo 17.09.2012 | | Autor: | sissile |
| Aufgabe | Wir hatten einen Satz:
Seien m,n [mm] \in \IN, \{r_1,..,r_{\phi(m)}\} [/mm] ein primes Restsystem modulo m, [mm] \{s_1,..,s_{\phi(n)}\} [/mm] ein primes Restsystem modulo n und ggT(m,n)=1. Dann ist [mm] \{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\} [/mm] ein primes Restsystem modulo mn.
[mm] \phi(m) [/mm] ist die Eulersche [mm] \phi-Funktion
[/mm]
[mm] \phi(m) [/mm] = Anzahl [mm] \{ k \in \IZ| 0 <=k<=m-1, ggT(k,m)=1\} [/mm] |
Hallo,
Wieso folgt aus den Satz dass:
Wenn m,n [mm] \in \IN [/mm] und ggT(m,n)=1, dann gilt [mm] \phi(mn) [/mm] = [mm] \phi(m) \phi(n)
[/mm]
Mir ist das leider nicht klar.
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:01 Mo 17.09.2012 | | Autor: | hippias |
> Wir hatten einen Satz:
> Seien m,n [mm]\in \IN, \{r_1,..,r_{\phi(m)}\}[/mm] ein primes
> Restsystem modulo m, [mm]\{s_1,..,s_{\phi(n)}\}[/mm] ein primes
> Restsystem modulo n und ggT(m,n)=1. Dann ist [mm]\{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\}[/mm]
> ein primes Restsystem modulo mn.
>
> [mm]\phi(m)[/mm] ist die Eulersche [mm]\phi-Funktion[/mm]
> [mm]\phi(m)[/mm] = Anzahl [mm]\{ k \in \IZ| 0 <=k<=m-1, ggT(k,m)=1\}[/mm]
>
> Hallo,
>
> Wieso folgt aus den Satz dass:
> Wenn m,n [mm]\in \IN[/mm] und ggT(m,n)=1, dann gilt [mm]\phi(mn)[/mm] =
> [mm]\phi(m) \phi(n)[/mm]
> Mir ist das leider nicht klar.
>
>
> Liebe Grüße
Es genuegt zu zeigen , dass [mm] $\{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\}$ [/mm] genau [mm] $\phi(n)\phi(m)$ [/mm] Elemente hat, denn weil nach obigem Satz ja [mm] $\phi(nm)= |\{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\}|$ [/mm] gilt, waere dann die Behauptung gezeigt. Dazu ueberlege Dir, dass die Zahlen $n [mm] r_i [/mm] + m [mm] s_j$ [/mm] alle verschieden sind, d.h. mache den Ansatz $n [mm] r_i [/mm] + m [mm] s_j= [/mm] n [mm] r_k [/mm] + m [mm] s_l$ [/mm] und schliese [mm] $r_i= r_k$ [/mm] und [mm] $s_j= s_l$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:24 Mi 19.09.2012 | | Autor: | sissile |
Der Beweis des Satzes ist schon klar, wo du mir den Ansatz gibst
[mm] \{r_1,..,r_{\phi(m)} \} [/mm] hat [mm] \phi(m) [/mm] Elemente
[mm] \{s_1,..,s_{\phi(n)} \} [/mm] hat [mm] \phi(n) [/mm] Elemente
$ [mm] \{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\} [/mm] $ hat [mm] \phi(m)\phi(n) [/mm] Elemente
Und nach dem Satz, den wir in der Vorlesung bewiesen haben sind das alles prime Restsysteme.
[mm] \{r_1,..,r_{\phi(m)} \} [/mm] mod m
[mm] \{s_1,..,s_{\phi(n)} \} [/mm] mod n
$ [mm] \{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\} [/mm] mod mn
Wieso folgt aber nun [mm] \phi(m) [/mm] * [mm] \phi(n) [/mm] = [mm] \phi(m*n)?
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:54 Mi 19.09.2012 | | Autor: | hippias |
> Der Beweis des Satzes ist schon klar, wo du mir den Ansatz
> gibst
>
> [mm]\{r_1,..,r_{\phi(m)} \}[/mm] hat [mm]\phi(m)[/mm] Elemente
> [mm]\{s_1,..,s_{\phi(n)} \}[/mm] hat [mm]\phi(n)[/mm] Elemente
> [mm]\{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\}[/mm]
> hat [mm]\phi(m)\phi(n)[/mm] Elemente
>
> Und nach dem Satz, den wir in der Vorlesung bewiesen haben
> sind das alles prime Restsysteme.
> [mm]\{r_1,..,r_{\phi(m)} \}[/mm] mod m
> [mm]\{s_1,..,s_{\phi(n)} \}[/mm] mod n
> $ [mm]\{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\}[/mm]
> mod mn
>
> Wieso folgt aber nun [mm]\phi(m)[/mm] * [mm]\phi(n)[/mm] = [mm]\phi(m*n)?[/mm]
Wenn der Satz gilt, bildet die Menge $R:= [mm] \{n r_i + m s_j | 1 <= i <= \phi(m),1 <= j <= \phi(n)\}$ [/mm] ein Vertretersystem fuer die primen Restklassen Modulo $nm$. Damit ist nach Definition der [mm] $\phi$ [/mm] Funktion $|R|= [mm] \phi(nm)$. [/mm] Zaehlst Du die Elemente in $R$ aber direkt aus, so erhaelst Du $|R|= [mm] \phi(n)\phi(m)$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:47 Mi 19.09.2012 | | Autor: | sissile |
Hallo,
Danke jetzt hab ich es verstanden;)
Liebe Grüße,
|
|
|
|
