Euler und Fermat < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:43 Do 06.11.2008 | | Autor: | Riley |
| Aufgabe | Die Eulersche phi-Funktion [mm] \phi: \mathbb{N}-\{1\} \rightarrow \mathbb{N } [/mm] ist definiert durch [mm] \phi(m) [/mm] = [mm] |(\mathbb{Z} [/mm] / m [mm] \mathbb{Z})^{\*}|.
[/mm]
Zeigen Sie folgende Verallgemeinerung des kleinen Satzes von Fermat:
Seien m [mm] \in \mathbb{N} [/mm] und a [mm] \in \mathbb{Z} [/mm] mit ggT(a,m) =1. Dann ist
[mm] a^{\phi(m)} \equiv [/mm] 1 mod m. |
Hallo,
wie kann man sich die Funktion [mm] \phi [/mm] vorstellen? Wird durch sie m auf die entsprechende Einheit in [mm] \mathbb{Z} [/mm] / m [mm] \mathbb{Z} [/mm] abgebildet?
Habt ihr einen Hinweis wie man diese Aufgabe lösen kann?
... das wäre wirklich super.
Viele Grüße,
Riley
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:24 Do 06.11.2008 | | Autor: | Fry |
Hi,
also [mm] \phi(m) [/mm] gibt die Anzahl der zu m teilerfremden Zahlen zwischen 1 und m an. Dies ist gleichbedeutend mit der Anzahl der Einheiten in [mm] \IZ/n\IZ=|(\IZ/n\IZ)^{\*}|. [/mm]
[mm] (\IZ/n\IZ)^{\*}= [/mm] Menge der Einheiten in [mm] \IZ/n\IZ.
[/mm]
Man kann einfach beweisen: [mm] ggT(a,n)=1\gdw [/mm] a [mm] \in(\IZ/n\IZ)^{\*}, [/mm] also a Einheit in [mm] \IZ/n\IZ.
[/mm]
Beweis:
[mm] ggT(a,n)=1\gdw1=ax+ny(x,y\in\IZ)\Rightarrow1=ax [/mm] in [mm] \IZ/n\IZ \gdw [/mm] a ist Einheit in [mm] \IZ/n\IZ
[/mm]
Wenn du nun den Satz beweisen willst, solltest du den Satz von Lagrange und seine Folgerungen betrachten. Und zwar gilt:
Sei G Gruppe, [mm] a\in [/mm] G. Dann gilt [mm] a^{|G|}=e [/mm]
Entsprechend [mm] a^{\phi(n)}=1 [/mm] in [mm] \IZ/n\IZ [/mm] ,wobei [mm] a\in(\IZ/n\IZ)^{\*}
[/mm]
Jetzt eigentlich nur noch die Gleichung in eine Kongruenz umwandeln. Fertig !
Viele Grüße
Christian
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:45 So 09.11.2008 | | Autor: | Riley |
Hi Christian,
ah das ist cool, vielen Dank für deine Erklärungen!
D.h. diese Gleichung
> Entsprechend [mm]a^{\phi(n)}=1[/mm] in [mm]\IZ/n\IZ[/mm] ,wobei
> [mm]a\in(\IZ/n\IZ)^{\*}[/mm]
ist schon gleichbedeutend mit [mm] a^{\phi(m)} \equiv [/mm] 1 mod n, denn das in Z durch m geteilt bleibt Rest 1 ?
Viele Grüße & besten Dank,
Riley
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:06 So 09.11.2008 | | Autor: | Fry |
Hi Riley,
ganz genau:
[mm] \overline{a} [/mm] = [mm] \overline{b} [/mm] in [mm] \IZ/n\IZ
[/mm]
[mm] a+n\IZ=b+n\IZ
[/mm]
[mm] \gdw a\equiv [/mm] b mod n
[mm] \gdw [/mm] n | a-b
hab in meiner Erklärung bei Gleichungen in [mm] \IZ/n\IZ [/mm] die "Restklassenstriche" übrigens immer aus Faulheit weggelassen ; ).
Grüße
Christian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:40 So 09.11.2008 | | Autor: | Riley |
Hallo Christian,
okay, alles klar. Vielen Dank nochmal!
Viele Grüße,
Riley
|
|
|
|
