Beweis Carmichael-Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:34 Do 17.11.2016 | | Autor: | MarcHe |
| Aufgabe | Sei $n>1$ ungerade mit Primfaktorzerlgung [mm] $n=p_1^{s_1}*...*p_r^{s_r}$. [/mm] Es sei [mm] $\lambda [/mm] (n) = [mm] kgV(\phi (p_1^{s_1}), [/mm] ..., [mm] \phi p_r^{s_r})$. [/mm]
a. Zeigen Sie: [mm] $a^{\lambda (n)}=1 [/mm] mod (n) $
b. $n$ ist genau dann eine Carmichael-Zahl, wenn gilt [mm] $\lambda [/mm] (n)|n-1$ |
Hallo,
zu a. habe ich den folgenden Ansatz:
Nach dem chinesischen Restsatz kann man [mm] $a^{\lambda (n)}=1 [/mm] mod (n) $ auch als eine Menge der folgenden Kongruenzen auffassen:
Es ist [mm] $\lambda (p_1^{s_i})= \phi (p_r^{s_i}) [/mm] = [mm] p_i^{s_i-1}(p_i-1)$, [/mm] sodass [mm] $a^{\lambda (p_1^{s_1})} [/mm] = 1 mod [mm] p_1^{s_1}$ [/mm] für jedes [mm] p_i^{s_i} [/mm] mit $1<=i<=r$ gilt. Es gilt [mm] $\lambda (p_1^{s_i})|\lambda [/mm] (n)$, sodass weiter [mm] $a^{\lambda(n)}=(a^{\lambda (p_1^{s_1})})^{k}=1^k [/mm] = 1 mod [mm] p_1^{s_1}$. [/mm] Damit folgt [mm] $a^{\lambda (n)}=1 [/mm] mod (n) $.
Passt das so?
Wie würde ich jetzt bei b. vorgehen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:42 Fr 18.11.2016 | | Autor: | sinnlos123 |
Hi!
es wäre schön, wenn du etwas größere Gleichungen machst. (ich kann da fast nix erkennen)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:32 So 20.11.2016 | | Autor: | felixf |
Moin Marc!
> Sei [mm]n>1[/mm] ungerade mit Primfaktorzerlgung
> [mm]n=p_1^{s_1}*...*p_r^{s_r}[/mm]. Es sei [mm]\lambda (n) = kgV(\phi (p_1^{s_1}), ..., \phi p_r^{s_r})[/mm].
>
> a. Zeigen Sie: [mm]a^{\lambda (n)}=1 mod (n)[/mm]
Was soll $a$ sein? Für $a = n$ gilt das schonmal ganz sicher nicht.
> b. [mm]n[/mm] ist genau
> dann eine Carmichael-Zahl, wenn gilt [mm]\lambda (n)|n-1[/mm]
>
> Hallo,
>
> zu a. habe ich den folgenden Ansatz:
>
> Nach dem chinesischen Restsatz kann man [mm]a^{\lambda (n)}=1 mod (n)[/mm]
> auch als eine Menge der folgenden Kongruenzen auffassen:
>
> Es ist [mm]\lambda (p_1^{s_i})= \phi (p_r^{s_i}) = p_i^{s_i-1}(p_i-1)[/mm],
> sodass [mm]a^{\lambda (p_1^{s_1})} = 1 mod p_1^{s_1}[/mm] für jedes
> [mm]p_i^{s_i}[/mm] mit [mm]1<=i<=r[/mm] gilt. Es gilt [mm]\lambda (p_1^{s_i})|\lambda (n)[/mm],
> sodass weiter [mm]a^{\lambda(n)}=(a^{\lambda (p_1^{s_1})})^{k}=1^k = 1 mod p_1^{s_1}[/mm].
> Damit folgt [mm]a^{\lambda (n)}=1 mod (n) [/mm].
>
> Passt das so?
Wenn du manchmal $1$ durch $i$ ersetzt, schon :)
> Wie würde ich jetzt bei b. vorgehen?
Die eine Richtung folgt ziemlich direkt aus $a$. Für die andere Richtung beachte: Die Aussage [mm] $\lambda(n) \mid [/mm] (n - 1)$ ist äquivalent zu [mm] $\phi(p_i^{e_i}) \mid [/mm] (n - 1)$ für alle $i$. Es reicht also aus, dass zu zeigst: wenn $n$ Carmichael-Zahl ist, dann gilt [mm] $\phi(p_i^{e_i}) \mid [/mm] (n - 1)$ für alle $i$.
Was weisst du über die multiplikative Gruppe modulo [mm] $p_i^{e_i}$?
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 08:33 Mo 21.11.2016 | | Autor: | MarcHe |
Hallo,
vielen Dank für deine Hilfe schonmal. Nochmal folgende Ergänzungen:
zu a: $ [mm] a^{\lambda (n)}=1 [/mm] mod (n) $ für alle $a [mm] \in (\IZ [/mm] /n [mm] \IZ)^{\times}$
[/mm]
zu b. habe ich nun folgenden Ansatz:
[mm] $\Rightarrow$ [/mm] Sei $n$ eine Carmichael-Zahl für die gilt [mm] $a^{n-1} \equiv [/mm] 1 (mod n)$ für alle $a [mm] \in (\IZ [/mm] /n [mm] \IZ)^{\times}$. [/mm] Nach a. gilt ebenso $ [mm] a^{\lambda (n)}=1 [/mm] mod (n) $. Da $ord(a) <= [mm] \lambda [/mm] (n) < n-1$ folgt [mm] $\lambda [/mm] (n)|n-1$. Ok?
[mm] $\Leftarrow$ [/mm] Sei [mm] $\lambda [/mm] (n)|n-1$ dann gilt ebenso [mm] $\lambda (p_i^{s_i}) [/mm] |(n-1)$ bzw. [mm] $\phi(p_i^{s_i}) [/mm] |(n-1)$ für $1<=i<=r$ (muss ich diese äquivalenz nochmal beweisen). Ab wann komme ich zu dem Punkt, dass $n$ eine Carmichael Zahl sein muss?
Wenn ich in b. statt $n$ Carmichael Zahl, sondern Primzahl sage. Komme ich zu folgendes:
[mm] $\Rightarrow$ [/mm] Sei $n$ eine Primzahl dann ist $ [mm] \lambda [/mm] (n)= [mm] \phi [/mm] (n) = n-1 $. Es folgt $n-1|n-1$.
[mm] $\Leftarrow$ [/mm] Hier habe ich das gleiche Problem wie oben. Wie komme ich zu der Erkenntnis, dass $n$ eine Primzahl sein muss?
Vielen Dank schonmal!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:20 Fr 25.11.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
