Euler/Beweis/ < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:12 Mo 17.09.2012 | | Autor: | sissile |
| Aufgabe | Sei m [mm] \in \IN, [/mm] a [mm] \in \IZ [/mm] und ggT(a,m)=1
dann gilt [mm] a^{\phi(m)} \equiv [/mm] 1 (m) |
Mir ist klar, dass der Beweis folgt aus dem Satz mit Anwenden auf [mm] \IZ^{\*}_m [/mm] (Menge aller Einheiten bzw. primen Restklassen):
Sei (G,*) eine endliche abelsche Gruppe der Ordnung |G| mit neutralem Element e. Dann gilt $ [mm] a^{|G|} [/mm] $ = e $ [mm] \forall [/mm] $ a $ [mm] \in [/mm] $ G
[mm] \overline{a}^{|\IZ^{\*}_m|}= \overline{a}^{\phi(m)}= \overline{1} [/mm]
[mm] \forall \overline{a}\in \IZ^{\*}_m
[/mm]
=> [mm] a^{\phi(m)}= [/mm] 1
Wozubrauche ich nun dass ggT(a,m)=1????
Liebe Grüße
|
|
| |
|
moin,
Was wäre denn, wenn [mm] $\ggT(a,m) [/mm] > 1$.
Dann hättest du [mm] $a^{\varphi(m)-1} \equiv a^{-1} \mod [/mm] m$.
Also ist [mm] $\ggT(a,m) [/mm] > 1$ und trotzdem ist $a$ eine Einheit in [mm] $\IZ_m$; [/mm] das sollte bei dir ein paar Alarmglocken läuten lassen.
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:10 Mo 17.09.2012 | | Autor: | sissile |
> wenn $ [mm] \ggT(a,m) [/mm] > 1 $.
> Dann hättest du $ [mm] a^{\varphi(m)-1} \equiv a^{-1} \mod [/mm] m $.
Hallo,
Was hast die Kongruenz mit den ggT(a,m) > 1 zu tun. Das verstehe ich nun nicht.
Liebe Grüße
|
|
|
| |
|
Ist [mm] $\ggT(a,m) [/mm] > 1$, so ist $a$ modulo $m$ nicht invertierbar, also $a [mm] \not\in \IZ_m^\*$.
[/mm]
Ist etwa $m=a*b$ für ein $1 < b < m$ (das kann man ja aus [mm] $\ggT(a,m)>1$ [/mm] folgern), so gilt $ab [mm] \equiv [/mm] 0 [mm] \mod [/mm] m$.
Wäre nun $a$ invertierbar, so gilt:
[mm] $a^{-1}ab \equiv [/mm] b [mm] \mod [/mm] m$ und auf der anderen Seite [mm] $a^{-1}ab \equiv a^{-1}*0 \equiv [/mm] 0 [mm] \mod [/mm] m$, also $b [mm] \equiv [/mm] 0$ und damit $b=0$ oder $b>m$, was aber ein Widerspruch zu $1 < b < m$ ist.
Dir sollte aber wenn du dich mit Einheitengruppen von [mm] $\IZ_m$ [/mm] rumschlägst eigentlich bereits klar sein, welche Elemente aus [mm] $\IZ_m$ [/mm] multiplikativ invertierbar sind und welche nicht...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:44 Mo 17.09.2012 | | Autor: | sissile |
Zur Verteidigung, ich habs erst heute gelernt ;)
Mir ist noch immer nicht klar:
> Ist etwa $ [mm] m=a\cdot{}b [/mm] $ für ein $ 1 < b < m $ (das kann man ja aus $ [mm] \ggT(a,m)>1 [/mm] $ folgern)
Wie folgerst du das?
aus $ [mm] \ggT(a,m)>1 [/mm] $ folgere ich [mm] \exists [/mm] p ..Primzahl sodass p|a, p|m
> Ist $ [mm] \ggT(a,m) [/mm] > 1 $, so ist $ a $ modulo $ m $ nicht invertierbar, also $ a [mm] \not\in \IZ_m^* [/mm] $.
Jap wenn ich das erste Zitat verstanden habe, ist mir das klar.
d.h.a ist keine primitive Restklasse.
d.h (->Umkehrschluss)widerum wenn a eine primitive Restklasse ist, ist ggT(a,m)=1
Läuft es darauf hinaus? ABer wieso muss a eine prime Restklasse sein für den Satz von EUler?
Liebe Grüße
|
|
|
| |
|
> Zur Verteidigung, ich habs erst heute gelernt ;)
Hmm, und du fängst gleich mit Ordnung der Einheitengruppe und so an? xD
> Mir ist noch immer nicht klar:
> > Ist etwa [mm]m=a\cdot{}b[/mm] für ein [mm]1 < b < m[/mm] (das kann man ja
> aus [mm]\ggT(a,m)>1[/mm] folgern)
> Wie folgerst du das?
Huch, da fehlte noch ein $k$.
Also $m*k = a*b$ für ein $k [mm] \in \IN$.
[/mm]
Sei $x := [mm] \ggT(a,m)$, [/mm] also insbesondere $x>1$.
Dann gibt es - da $x$ sowohl ein Teiler von $a$ als auch von $m$ ist, ein $k$ mit $a=x*k$ und ein $b$ mit $m=x*b$.
Berechnen wir nun $a*b$ so erhalten wir $a*b = k*m$ wie gewünscht.
Da sowohl $m [mm] \equiv [/mm] 0 [mm] \mod [/mm] m$ als auch $k*m [mm] \equiv [/mm] 0 [mm] \mod [/mm] m$ für jede natürliche Zahl $k$ stimmt der Rest meiner Behauptung aber dennoch.^^
Du darfst dir nochmal überlegen, wieso man aus $x>1$ auf $1 < b < m$, also $b [mm] \not \equiv [/mm] 0 [mm] \mod [/mm] m$ schließen kann (ggf. den Fall $x=m$ von Hand bearbeiten).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:32 Mi 19.09.2012 | | Autor: | sissile |
Hallo das ist mir nun klar.
Zur letzten Frage: weil m = x *b
So nun haben wir:
Ist a invertierbar, also eine Einheit mod m so folgt ggT(a,m)=1 => a prime Restklasse.
Was hat das nun mit dem Satz von euler zu tun?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:11 Mi 19.09.2012 | | Autor: | hippias |
> Hallo das ist mir nun klar.
> Zur letzten Frage: weil m = x *b
>
>
> So nun haben wir:
> Ist a invertierbar, also eine Einheit mod m so folgt
> ggT(a,m)=1 => a prime Restklasse.
> Was hat das nun mit dem Satz von euler zu tun?
>
Der Satz von Euler gilt ausschliesslich fuer $a$ mit $ggT(a,m)= 1$, d.h. nur fuer in [mm] $\IZ_{m}$ [/mm] invertierbare Elemente; fuer $a$ mit $ggT(a,m)>1$ ist er falsch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:33 Mi 19.09.2012 | | Autor: | sissile |
Ich danke euch beiden für die tatkräftige Hilfe.
Schönen Nachmittag ;)
|
|
|
|
