Restklassen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Fuer welches a [mm] \in [/mm] {0,1,...,n-1} gilt [mm] 7^{12121} \equiv [/mm] a (mod 9)? |
Hallo Leute,
ich komme nicht weiter bei dieser Aufgabe.
In der Vorlesung gab es ein Beispiel, dass zu dieser Aufgabe passt:
[mm] 6^{10000} \equiv (-1)^{10000} [/mm] (mod 7)
Hier wird sofort klar das 6 und 1 die gleichen Representanten der Klasse sind.
-1 laesst sich ausserdem auch super Potenzieren.
Habt ihr eine Idee, wie ich weiterkommen koennte?
Gruss
mathlooser
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:45 Sa 22.03.2014 | | Autor: | Teufel |
Hi!
Im Exponenten kannst du erst einmal mod [mm] \varphi(9) [/mm] (das ist die Gruppenordnung) rechnen.
|
|
|
| |
|
Hallo Teufel
wow, das ging ja schnell.
ok also:
12121 : 9 = 1346 r 7
Der Exponent ist immer noch recht gross.
Der entstehende Rest 7 entspricht zwar der Loesung, also a = 7, das muss aber nur Zufall sein, weil es bei einer anderen Aufgabe nicht klappt.
Gruss
mathlooser
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:45 Sa 22.03.2014 | | Autor: | Teufel |
Nein, du hast ja nur mod 9 gerechnet, aber du musst im Exponenten mod [mm] \varphi(9) [/mm] rechnen [mm] (\varphi [/mm] = Eulersche Phifunktion). Hattet ihr die schon?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:05 Sa 22.03.2014 | | Autor: | mathlooser |
Oh, danke fuer den Tipp.
Wir hatten die Eulerfunktion zwar nicht in der Vorlesung, die steht aber im Skript. ich schau mir die mal eben an.
Gruss
mathlooser
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:11 Sa 22.03.2014 | | Autor: | Teufel |
Ok, na ja so wichtig ist die Funktion hier auch nicht. Wichtig ist, dass "Element hoch Gruppenordnung = neutrales Element" gilt, denn deswegen darfst du im Exponenten modulo Gruppenordnung rechnen. Die Gruppenordnung kannst du dir auch so, ohne die Phifunktion, klar machen. Wie viele Elemente gibt es in [mm] \IZ_9^\*? [/mm]
|
|
|
| |
|
Hallo Teufel,
war gerade noch mit einer anderen Aufgabe beschaeftigt.
> Wie viele Elemente gibt es in [mm] \IZ^\times_{9}?
[/mm]
Also die Anzahl aller invertierbaren El. aus [mm] \IZ_{9}, [/mm] oder?
[mm] |\IZ^\times_{9}| [/mm] = 6, weil
Im Skript steht: [mm] \overline{a} \in \IZ^\times_{n} \gdw [/mm] ggT(a,n) = 1
[mm] \IZ^\times_{9} [/mm] = { [mm] \overline{1},\overline{2},\overline{4},\overline{5},\overline{7},\overline{8} [/mm] }
> Wichtig ist, dass "Element hoch Gruppenordnung = neutrales Element" gilt
Gruppenordnung waere in meinem Fall die 9 oder?
Gruss
mathlooser
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:41 So 23.03.2014 | | Autor: | Teufel |
Genau, [mm] |\IZ_9^\times|=6, [/mm] also ist die Gruppenordnung 6 und nicht 9. ;) Das heißt, dass du im Exponenten modulo 6 rechnen darfst. Ist dir klar, warum das geht?
|
|
|
| |
|
Villeicht wegen:
> "Element hoch Gruppenordnung = neutrales Element"
:)?
[mm] \overline{a}^{6} [/mm] = [mm] \overline{1}
[/mm]
[mm] \overline{a}^{6} [/mm] muss also durch 9 mit Rest 1 teilbar sein, damit ich modulo 6 im Exponenten rechnen darf?
Offenbar gilt [mm] \overline{a}^{6} [/mm] = [mm] \overline{1} \gdw [/mm] a = [mm] \overline{1}
[/mm]
Dann darf ich 12121 : 6 = 2020 r 1 rechnen.
Ich verstehe nicht warum ich Exponent durch mod 6 rechnen darf, wenn die o.g. Bed. gilt.
Ausserdem habe ich immer noch 2020 im Exp. stehen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:30 So 23.03.2014 | | Autor: | Teufel |
Ja, also in deinem Fall gilt [mm] $a^6=1$. [/mm] Allgemein: Sei G eine endliche Gruppe mit |G|=n. Dann gilt für alle [mm] $g\in [/mm] G$: [mm] $g^n=1$.
[/mm]
Nun gilt: [mm] $a^{12121}=a^{2020*6+1}=\underbrace{(a^{2020})^6}_{=1}*a^1=a \mod [/mm] 9$.
Du brauchst also nur den Rest beim Teilen durch die Gruppenordnung 6, hier also Rest 1.
|
|
|
| |
|
Hallo Teufel,
danke erstmal fuer deinen Einsatz.
Ich bin mittlerweile leicht verwirrt.
Ich versuche mal ein wenig zusammenzufassen:
> Im Exponenten kannst du erst einmal mod $ [mm] \varphi(9) [/mm] $ (das ist die Gruppenordnung) rechnen.
Warum darf ich im Exponent [mm] \varphi(9) [/mm] rechnen?
> Wichtig ist, dass "Element hoch Gruppenordnung = neutrales Element"
> gilt, denn deswegen darfst du im Exponenten modulo Gruppenordnung rechnen.
Wie komme ich auf "Element hoch Gruppenordnung = neutrales Element" und woher weiss ich dass ich es im Exponenten anwenden darf?
> Die Gruppenordnung kannst du dir auch so, ohne die Phifunktion, klar machen.
> Wie viele Elemente gibt es in $ [mm] \IZ_9^*? [/mm] $
Ich hab mir die Eulersche Funktion mal angesehn. Die Eulersche Funktion gibt die Anzahl aller invertierbaren Elemente (= Einheiten) aus [mm] \IZ_9^\times [/mm] an. Offenbar gilt Gruppenordnung = [mm] \varphi(n) [/mm] richtig?
Ich weiss jetzt, dass [mm] \varphi(9) [/mm] = 6, das habe ich aber nicht ausgerechnet, sondern aufgrund folgender Tatsache gesehen/angewendet: $ [mm] \overline{a} \in \IZ^\times_{n} \gdw [/mm] $ ggT(a,n) = 1
Wie berechne ich die Gruppenordnung?
> Ja, also in deinem Fall gilt $ [mm] a^6=1 [/mm] $. Allgemein: Sei G eine endliche
> Gruppe mit |G|=n. Dann gilt für alle $ [mm] g\in [/mm] G $: $ [mm] g^n=1 [/mm] $.
ok, aber warum gilt [mm] g\in [/mm] G $: $ [mm] g^n=1 [/mm] bzw wie komme ich darauf?
Und letzte Frage:
> Nun gilt: $ [mm] a^{12121}=a^{2020\cdot{}6+1}=\underbrace{(a^{2020})^6}_{=1}\cdot{}a^1=a \mod [/mm] 9 $.
Hier weird also erst mod 6 im Exponenten gerechnet und der Rest "getrennt". Woher weiss ich, dass [mm] (a^{2020})^{6} [/mm] = 1 ist?
Ich konnte ausserdem anhand des Skripts noch rauskriegen, dass wegen des kleinen Satzes von Fermat folgendes gilt: Falls n aus [mm] \IZ_n [/mm] eine Primzahl ist, so gilt [mm] \varphi(n) [/mm] = n-1
Da es sich in meiner Aufgabe nicht um eine Primzahl handelt, gibt es auch keine 9-1 = 8 Einheiten aus [mm] \IZ^\times_{9}, [/mm] sondern 6.
Gruss
mathlooser
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:21 So 23.03.2014 | | Autor: | Teufel |
Hi!
Bestimmt hattet ihr irgendwo mal den Satz, dass [mm] $g^n=1$ [/mm] ist, falls [mm] $g\in [/mm] G$ und $|G|=n$, G Gruppe ist. Schau am besten noch einmal die Unterlagen durch.
Das mit der Eulerschen Phifunktion ist hier auch relativ egal, wenn ihr die schon besprochen hättet, hätte ich es damit erklärt, aber man braucht sie hier nicht. Vergiss den Teil am besten ;)
Das einzige was du wirklich brauchst, ist dieser allgemeine Satz von oben. Die Gruppenordnung ist hier 6, das hast du ja auch so herausbekommen. Nach dem Satz ist also [mm] $b^6=1$ [/mm] für alle [mm] $b\in \IZ_9^\times$. [/mm] Damit ist dann aber auch [mm] $(\underbrace{a^{2020}}_{=:b})^6=1$. a^{2020} [/mm] ist ja nur irgendein Element deiner Gruppe.
Wenn ihr den Satz von oben nicht hattet: Habt ihr mal gezeigt, dass die Ordnungen von Untergruppen die Ordnung der größeren Gruppe teilen? Damit kann man das leicht zeigen.
|
|
|
| |
|
Hi,
> Bestimmt hattet ihr irgendwo mal den Satz, dass [mm]g^n=1[/mm] ist,
> falls [mm]g\in G[/mm] und [mm]|G|=n[/mm], G Gruppe ist. Schau am besten noch
> einmal die Unterlagen durch.
hierzu finde ich leider nichts.
> Das mit der Eulerschen Phifunktion ist hier auch relativ
> egal, wenn ihr die schon besprochen hättet, hätte ich es
> damit erklärt, aber man braucht sie hier nicht. Vergiss
> den Teil am besten ;)
ok :)
> Das einzige was du wirklich brauchst, ist dieser
> allgemeine Satz von oben.
hast du villeicht ein Stichwort dazu?
> Die Gruppenordnung ist hier 6,
> das hast du ja auch so herausbekommen. Nach dem Satz ist
> also [mm]b^6=1[/mm] für alle [mm]b\in \IZ_9^\times[/mm]. Damit ist dann aber
> auch [mm](\underbrace{a^{2020}}_{=:b})^6=1[/mm]. [mm]a^{2020}[/mm] ist ja nur
> irgendein Element deiner Gruppe.
Super, das hab ich jetzt verstanden.
> Wenn ihr den Satz von oben nicht hattet: Habt ihr mal
> gezeigt, dass die Ordnungen von Untergruppen die Ordnung
> der größeren Gruppe teilen? Damit kann man das leicht
> zeigen.
Ist hier eigentlich die Rede von (partiellen) Ordnungen, also eine Relation?
Zu Untergruppen haben wir:
De nition. Es sei (G; *) eine Gruppe. Eine Teilmenge H [mm] \subseteq [/mm] G heisst Untergruppe von G, geschr. H [mm] \le [/mm] G, wenn gilt:
(U1) e [mm] \in [/mm] H.
(U2) Fuer alle x; y [mm] \in [/mm] H ist auch x * [mm] y^{-1} \in [/mm] H. (H ist abgeschlossen bzgl. *)
In diesem Fall ist H selbst eine Gruppe bzgl. der Verknupfung * aus G.
|
|
|
| |
|
Hi,
> Hi,
>
> > Bestimmt hattet ihr irgendwo mal den Satz, dass [mm]g^n=1[/mm] ist,
> > falls [mm]g\in G[/mm] und [mm]|G|=n[/mm], G Gruppe ist. Schau am besten noch
> > einmal die Unterlagen durch.
>
> hierzu finde ich leider nichts.
Satz von Lagrange, bzw. eine Folgerung davon.
> > Das mit der Eulerschen Phifunktion ist hier auch relativ
> > egal, wenn ihr die schon besprochen hättet, hätte ich es
> > damit erklärt, aber man braucht sie hier nicht. Vergiss
> > den Teil am besten ;)
>
> ok :)
>
> > Das einzige was du wirklich brauchst, ist dieser
> > allgemeine Satz von oben.
>
> hast du villeicht ein Stichwort dazu?
>
> > Die Gruppenordnung ist hier 6,
> > das hast du ja auch so herausbekommen. Nach dem Satz ist
> > also [mm]b^6=1[/mm] für alle [mm]b\in \IZ_9^\times[/mm]. Damit ist dann aber
> > auch [mm](\underbrace{a^{2020}}_{=:b})^6=1[/mm]. [mm]a^{2020}[/mm] ist ja nur
> > irgendein Element deiner Gruppe.
>
> Super, das hab ich jetzt verstanden.
>
> > Wenn ihr den Satz von oben nicht hattet: Habt ihr mal
> > gezeigt, dass die Ordnungen von Untergruppen die Ordnung
> > der größeren Gruppe teilen? Damit kann man das leicht
> > zeigen.
>
> Ist hier eigentlich die Rede von (partiellen) Ordnungen,
> also eine Relation?
Nein. Ordnung im Sinne von Mächtigkeit.
> Zu Untergruppen haben wir:
>
> De nition. Es sei (G; *) eine Gruppe. Eine Teilmenge H
> [mm]\subseteq[/mm] G heisst Untergruppe von G, geschr. H [mm]\le[/mm] G,
> wenn gilt:
>
> (U1) e [mm]\in[/mm] H.
> (U2) Fuer alle x; y [mm]\in[/mm] H ist auch x * [mm]y^{-1} \in[/mm] H. (H
> ist abgeschlossen bzgl. *)
>
> In diesem Fall ist H selbst eine Gruppe bzgl. der
> Verknupfung * aus G.
|
|
|
|
