Der "Kleine Fermat" < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei n [mm] \ge [/mm] 2 eine natürliche Zahl. Wir betrachten die Einheitengrp. [mm] (\IZ [/mm] /(n))* des Ringes [mm] \IZ [/mm] /(n). Wir bezeichnen mit [mm] \phi(n) [/mm] die Ordnung von [mm] (\IZ [/mm] /(n))*.
i) Zeigen sie, dass für alle u [mm] \in (\IZ [/mm] /(n))* die Gleichung [mm] u^{\phi (n)}=1 [/mm] gilt.
ii) Berechnen sie [mm] \phi(p), [/mm] wobei p eine Primzahl sei.
iii) Zeigen sie, dass für alle ganzen Zahlen a und eine Primzahl p die Kongruenz [mm] a^p \equiv [/mm] a mod p gilt. Es ist also z.z, dass [mm] a^p [/mm] -a [mm] \in [/mm] (p) ist. |
Hallo,
so dann will ich mir das am Bsp. mal etwas deutlicher machen:
n=5:
[mm] (\IZ /5\IZ)= [/mm] { 0,1,2,3,4 }
[mm] (\IZ /5\IZ) [/mm] * = { 1,2,3,4} [mm] \Rightarrow \phi(5)=4
[/mm]
[mm] u^4 [/mm] :
[mm] 1^4=1 [/mm]
[mm] 2^4=16=1 [/mm]
[mm] 3^4=81=1 [/mm]
[mm] 4^4=256=1
[/mm]
Habe ich das richtig verstanden?
mittlerweile noch ne Frage aufgetaucht. Also wenn ich recht habe, dann verstehe ich nicht: Die Einheitengrp. ist doch Untergruppe von [mm] (\IZ [/mm] /(n)), oder? Aber dann passt hier der Satz von Lagragne nicht. Oder werfe ich hier gerade Sachen durcheinander? Weil ich mit n=5 ja ne Primzahl habe und dann können Untergrp. doch nur aus einem bzw. fünf Elementen bestehen, oder?
|
|
| |
|
> Sei n [mm]\ge[/mm] 2 eine natürliche Zahl. Wir betrachten die
> Einheitengrp. [mm](\IZ[/mm] /(n))* des Ringes [mm]\IZ[/mm] /(n). Wir
> bezeichnen mit [mm]\phi(n)[/mm] die Ordnung von [mm](\IZ[/mm] /(n))*.
>
> i) Zeigen sie, dass für alle u [mm]\in (\IZ[/mm] /(n))* die
> Gleichung [mm]u^{\phi (n)}=1[/mm] gilt.
> ii) Berechnen sie [mm]\phi(p),[/mm] wobei p eine Primzahl sei.
> iii) Zeigen sie, dass für alle ganzen Zahlen a und eine
> Primzahl p die Kongruenz [mm]a^p \equiv[/mm] a mod p gilt. Es ist
> also z.z, dass [mm]a^p[/mm] -a [mm]\in[/mm] (p) ist.
>
>
> Hallo,
>
> so dann will ich mir das am Bsp. mal etwas deutlicher
> machen:
>
> n=5:
> [mm](\IZ /5\IZ)=[/mm] { 0,1,2,3,4 }
> [mm](\IZ /5\IZ)[/mm] * = { 1,2,3,4} [mm]\Rightarrow \phi(5)=4[/mm]
>
> [mm]u^4[/mm] :
> [mm]1^4=1[/mm]
> [mm]2^4=16=1[/mm]
> [mm]3^4=81=1[/mm]
> [mm]4^4=256=1[/mm]
>
> Habe ich das richtig verstanden?
Ja genauso! Aber 5 ist langweilig, da es eine Primzahl ist. Kannst ja noch einmal [mm] $(\IZ/8\IZ)^\star:=\{\pm 1+8\IZ,\pm 3+8\IZ\}$ [/mm] probieren.
>
> mittlerweile noch ne Frage aufgetaucht. Also wenn ich recht
> habe, dann verstehe ich nicht: Die Einheitengrp. ist doch
> Untergruppe von [mm](\IZ[/mm] /(n)), oder?
Nein ist sie nicht!
> Aber dann passt hier der
> Satz von Lagragne nicht. Oder werfe ich hier gerade Sachen
> durcheinander?
Ja
> Weil ich mit n=5 ja ne Primzahl habe und
> dann können Untergrp. doch nur aus einem bzw. fünf
> Elementen bestehen, oder?
Eine Untergruppe von was?
[mm] $(\IZ/5\IZ)^\star$ [/mm] hat doch die Ordnung 4. Also gibt es eine Untergruppe der Ordnung 1 und 2.
|
|
|
| |
|
So ich habe mir jetzt überlegt:
[mm] (\IZ [/mm] /(n)) * ist endlich [mm] \Rightarrow [/mm] ord(u) ist endlich mit u [mm] \in (\IZ [/mm] /(n)) *
Satz von Lagrange: ord(u) | | [mm] (\IZ [/mm] /(n)) *|=k= [mm] \phi(n)
[/mm]
[mm] \Rightarrow [/mm] ord(u) [mm] \le [/mm] k sei [mm] k=p_1 [/mm] * [mm] p_2
[/mm]
[mm] \Rightarrow [/mm] sei [mm] ord(u)=p_1
[/mm]
[mm] \Rightarrow u^{p_1}=1 \Rightarrow (u^{p_1})^{p_2}=u^{p{1}*p_{2}}=u^k=1^{p_2}=1
[/mm]
Bin ich da auf dem richtigen Weg?
|
|
|
| |
|
> So ich habe mir jetzt überlegt:
>
> [mm](\IZ[/mm] /(n)) * ist endlich [mm]\Rightarrow[/mm] ord(u) ist endlich mit
> u [mm]\in (\IZ[/mm] /(n)) *
> Satz von Lagrange: ord(u) | | [mm](\IZ[/mm] /(n)) *|=k= [mm]\phi(n)[/mm]
Das ist auf jeden Fall der Ansatz.
>
> [mm]\Rightarrow[/mm] ord(u) [mm]\le[/mm] k sei [mm]k=p_1[/mm] * [mm]p_2[/mm]
Es kann doch auch [mm]k=p_1*p_2*p_3[/mm] sein.
>
> [mm]\Rightarrow[/mm] sei [mm]ord(u)=p_1[/mm]
> [mm]\Rightarrow u^{p_1}=1 \Rightarrow (u^{p_1})^{p_2}=u^{p{1}*p_{2}}=u^k=1^{p_2}=1[/mm]
Ja für den Fall [mm]k=p_1*p_2[/mm] geht das.
>
> Bin ich da auf dem richtigen Weg?
Der Ansatz ist in jedem Fall goldrichtig.
Dein Text allgemeiner formuliert ist:
Sei G eine endliche Gruppe der Ordnung n, dann gilt für alle [mm]g\in G[/mm] [mm]g^n=e[/mm].
Das kann man noch kurz begründen, indem man sich ein Element [mm]g\in G[/mm] mit Ordnung [mm]ord(g)=a[/mm] und genauso weiter macht, wie du angefangen hast mit [mm] $\;n=a*b$.
[/mm]
Das gilt dann allgemein, wobei man aufpassen muss, da [mm]\overline{a}\in (\IZ/p\IZ)^\star[/mm] nur gilt , sofern ggT(a,p)=1 ist. Mit [mm] $\overline{a}$ [/mm] ist Repräsentant von a.
|
|
|
| |
|
Danke!
So nun mal ii) :
ich habe mir überlegt:
[mm] u^{\phi(p)}=1 \gdw u^{\phi(p)}-1=0 [/mm]
[mm] \Rightarrow u^{\phi(p)}-1 [/mm] | p
[mm] \Rightarrow u^{\phi(p)}-1=1 [/mm] oder [mm] u^{\phi(p)}-1=p
[/mm]
[mm] u^{\phi(p)}-1=p \gdw u^{\phi(p)}=p+1 \gdw ln(u^{\phi(p)}) =\phi(p)*ln(u)=ln(p+1) \gdw \phi(p)=\bruch{ln(p+1)}{ln(u)}
[/mm]
Jetzt müsste man ja nur noch einen Wert für u kennen und dann könnte man die Gleichung lösen...ich dachte zunächst an die "1", aber die geht nicht, weil man dann durch "0" dividieren würde und das geht ja nicht. Und nun weiss ich gerade nicht weiter, vielleicht liege ich ja auch völlig daneben. Deshalb würde ich mich über Hinweise sehr freuen.
|
|
|
| |
|
> Danke!
>
> So nun mal ii) :
>
> ich habe mir überlegt:
>
> [mm]u^{\phi(p)}=1 \gdw u^{\phi(p)}-1=0[/mm]
Woraus ist u? Wenn [mm]u\in (\IZ/p\IZ)^\star[/mm] ist, dann steht dort eine Kongruenz und keine Gleichheit.
> [mm]\Rightarrow u^{\phi(p)}-1[/mm] | p
> [mm]\Rightarrow u^{\phi(p)}-1=1[/mm] oder [mm]u^{\phi(p)}-1=p[/mm]
Wenn [mm]u^{\varphi(p)}=1[/mm], dann geht doch [mm]u^{\varphi(p)}-1=1[/mm] niemals.
>
> [mm]u^{\phi(p)}-1=p \gdw u^{\phi(p)}=p+1 \gdw ln(u^{\phi(p)}) =\phi(p)*ln(u)=ln(p+1) \gdw \phi(p)=\bruch{ln(p+1)}{ln(u)}[/mm]
Nein. Leider nicht.
Der Ansatz könnte sein:
[mm]\varphi(n) \; := \; | \{a\in\IN \, |\, 1 \le a \le n \wedge\operatorname{ggT}(a,n) = 1 \}|[/mm]
Das sind dann auch genau die Elemente [mm]a+n\IZ[/mm], die in [mm](\IZ/n\IZ)^\star[/mm] vorkommen.
|
|
|
| |
|
Wie kommt man denn hier auf:
>
> Der Ansatz könnte sein:
>
> [mm]\varphi(n) \; := \; | \{a\in\IN \, |\, 1 \le a \le n \wedge\operatorname{ggT}(a,n) = 1 \}|[/mm]
>
Ich kann das nicht nachvollziehen...
ich glaube, ich habs (habe einfach noch einige einheitengrp. notiert und dann gesehen, wie sie sich zusammen setztn, nämlich genau so, wie du es aufgeschrieben hast. Danke!):
mit dem angegebenen Ansatz [mm] \Rightarrow \phi(n)
ggt(a,p)=1 gilt ja für alle zahlen p-1 [mm] \in \IN, [/mm] also [mm] \phi(p)=p-1
[/mm]
Richtig?
Hatte dann für iii) notiert:
[mm] \phi(p)=p-1 \Rightarrow a^{\phi(p)}=a^{p-1}=1
[/mm]
[mm] a^p=a^{p-1+1}=a^{p-1}*a^1=1*a
[/mm]
[mm] \Rightarrow a^p=a \equiv [/mm] a mod p
Richtig?
|
|
|
| |
|
> Wie kommt man denn hier auf:
> >
> > Der Ansatz könnte sein:
> >
> > [mm]\varphi(n) \; := \; | \{a\in\IN \, |\, 1 \le a \le n \wedge\operatorname{ggT}(a,n) = 1 \}|[/mm]
>
> >
>
> Ich kann das nicht nachvollziehen...
>
> ich glaube, ich habs (habe einfach noch einige
> einheitengrp. notiert und dann gesehen, wie sie sich
> zusammen setztn, nämlich genau so, wie du es
> aufgeschrieben hast. Danke!):
>
> mit dem angegebenen Ansatz [mm]\Rightarrow \phi(n)
> ggt(a,p)=1
> ggt(a,p)=1 gilt ja für alle zahlen p-1 [mm]\in \IN,[/mm] also
> [mm]\phi(p)=p-1[/mm]
>
> Richtig?
Ja!
>
>
> Hatte dann für iii) notiert:
>
> [mm]\phi(p)=p-1 \Rightarrow a^{\phi(p)}=a^{p-1}=1[/mm]
Die Frage ist nur, [mm] $a^{p-1}=1$ [/mm] verwenden darfst. Aber ohne geht es glaube ich nicht wirklich.
>
> [mm]a^p=a^{p-1+1}=a^{p-1}*a^1=1*a[/mm]
> [mm]\Rightarrow a^p=a \equiv[/mm] a mod p
>
> Richtig?
>
Das Ergebnis stimmt. Ob du hier den kleinen Fermat verwenden darfst, weiß ich noch nicht. Ich hätte jetzt eher ein [mm] $a\in(\IZ/p\IZ)^\star$ [/mm] genommen und dann deine Argumentation geliefert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:25 Mo 25.06.2012 | | Autor: | Big_Head78 |
Danke!
Das [mm] a^{p-1}=1 [/mm] hatte ich doch in Teil i) zu zeigen, also kann ich das hier doch bestimmt dann auch verwenden?!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:40 Mo 25.06.2012 | | Autor: | wieschoo |
War ja auch nur eine Empfehlung auch noch explizit zu schreiben, dass [mm] $a\in(\IZ/p\IZ)^\star$ [/mm] ist und somit auch insbes. ggT(a,p)=1
Und was ist mit dem Fall a=p. Nach (i) müssen ja a und p teilerfremd sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:18 Mo 25.06.2012 | | Autor: | Big_Head78 |
Kann a=p denn überhaupt vorkommen, denn in der einheitengrp. kommt p selbt doch gar nicht vor, das ist mir jetzt gerade gar nicht klar.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:34 Mo 25.06.2012 | | Autor: | wieschoo |
Na in der Einheitengruppe kann das natürlich nicht vorkommen. ABER:
"Zeigen sie, dass für alle ganzen Zahlen a und eine Primzahl p die Kongruenz a mod p gilt."
|
|
|
|
