Ordnung, Primitvwurzel < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe 1 | | Geben Sie für jedes [mm] a\in\IN [/mm] mit [mm] 1\le [/mm] a < 22 und ggT(a,22)=1 die Ordnung von a mod 22 an. |
| Aufgabe 2 | | Ermitteln Sie für [mm] n\in [/mm] {16,18} jeweils sämtliche Primitvwurzeln mod n. Für welche a und be [mm] \in\IZ [/mm] gilt [mm] ord_{18}(a)=3 [/mm] bzw. [mm] ord_{16}(b)=7? [/mm] |
hallo alle zusammen
zu nummer 1 habe ich nur eine rückfrage: zuerst haben wir uns überlegt, welche a´s in frage kommen und wie viele und haben dazu aufgeschrieben:
[mm] |\IZ [/mm] *_{22}|={1,3,5,7,9,13,15,17,19,21}
danach haben wir geguckt, welche werte die ordnung haben kann:
[mm] ord_{22}(a)|\varphi(22)=10
[/mm]
-> [mm] ord_{22}(a)\in{1,2,5,10}
[/mm]
dann haben wir die ordnungen bestimmt: [mm] ord_{22}(1)=1 [/mm] und dann alle weiteren potenzen der jeweiligen werte aus [mm] |\IZ [/mm] *_{22}| betrachtet, angefangen bei [mm] 3^{k}. [/mm] wir haben jetzt solange potenziert, bis 1 kam, also so: [mm] 3^{1}, 3^{2}, 3^{3}, 3^{4}, 3^{5} [/mm] usw.
meine frage ist jetzt: reicht es nicht aus, wenn man als potenzen nur die werte hier nimmt: [mm] ord_{22}(a)\in{1,2,5,10}, [/mm] also die 1,2,5,10?
zu aufg. 2verstehe ich den schluss nicht mehr wirkl.
wir haben zuerst alle primitivwurzeln (=PW) mod n gesucht und dabei herausgefunden, dass es für [mm] n\in [/mm] {16} keine gibt.
für [mm] n\in{18} [/mm] haben wir 5 als PW gefunden und um weitere zu finden, sind wir dann wie folgt vorgegangen (und ab hier verstehe ich es nicht mehr):
[mm] a\equiv 5^{k} [/mm] mod 18 mit ggT(k,6)=1 und [mm] 1\le k\le [/mm] 6, [mm] k\in\IN
[/mm]
=> [mm] a\equiv [/mm] 5 mod 18 oder [mm] a\equiv 5^{5} \equiv [/mm] 11 mod 18
=> 11 ist die zweite PW mod 18.
wie kommt man dadrauf? und wodran sieht man, dass 11 die zweite PW mod 18 ist? und wie kommt man auf das [mm] a\equiv 5^{5}\equiv [/mm] 11 mod 18, also die ^{5}?
zum letzten teil der aufgabe 2 ist mir gerade eine erleuchtung gekommen ;), hoffe, dass sie stimmt;) also für welche [mm] b\in\IZ [/mm] gilt [mm] ord_{16}(b)=7?
[/mm]
ich habe folgenden ansatz gemacht:
[mm] \varphi(16)=\varphi(2^{4})=8
[/mm]
[mm] |\IZ [/mm] *_{16}|={1,3,5,7,9,11,13,15}
[mm] ord_{16}(b)|8 ord_{16}(b)={1,2,4,8}
[/mm]
[mm] \varphi(\varphi(16))=\varphi(8)=2
[/mm]
[mm] ord_{16}(1)=1
[/mm]
betrachte Potenzen von [mm] 3^{k} [/mm] mit [mm] k\in\IN [/mm] ergibt [mm] ord_{16}(3)=4
[/mm]
[mm] ord_{16}(3^{k})=\bruch{4}{4,k} [/mm] =2
[mm] \gdw [/mm] ggT(4,k)=2 mit [mm] k\in{2,4}
[/mm]
[mm] \gdw a\equiv 3^{2}\equiv [/mm] 9 mod16 oder [mm] a\equiv 3^{4}\equiv [/mm] 1 mod 16
Für a=9 oder a=1 element aus [mm] \IZ [/mm] gilt [mm] ord_{16}(b)=2
[/mm]
=> [mm] 9^{2}\equiv [/mm] 1 mod 16 oder [mm] 1^{2}\equiv [/mm] 1 mod 16
verdammt, mir ist gerade aufgefallen, dass das doch falsch ist, oder!? :( denn ich muss ja wissen, wann [mm] ord_{16}(b)=7 [/mm] ist und nicht 2...
danke für eure hilfe!!! :)
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:47 So 10.07.2011 | | Autor: | felixf |
Moin!
> Geben Sie für jedes [mm]a\in\IN[/mm] mit [mm]1\le[/mm] a < 22 und
> ggT(a,22)=1 die Ordnung von a mod 22 an.
> Ermitteln Sie für [mm]n\in[/mm] {16,18} jeweils sämtliche
> Primitvwurzeln mod n. Für welche a und be [mm]\in\IZ[/mm] gilt
> [mm]ord_{18}(a)=3[/mm] bzw. [mm]ord_{16}(b)=7?[/mm]
> hallo alle zusammen
>
> zu nummer 1 habe ich nur eine rückfrage: zuerst haben wir
> uns überlegt, welche a´s in frage kommen und wie viele
> und haben dazu aufgeschrieben:
>
> [mm]|\IZ[/mm] *_{22}|={1,3,5,7,9,13,15,17,19,21}
>
> danach haben wir geguckt, welche werte die ordnung haben
> kann:
>
> [mm]ord_{22}(a)|\varphi(22)=10[/mm]
> -> [mm]ord_{22}(a)\in{1,2,5,10}[/mm]
>
> dann haben wir die ordnungen bestimmt: [mm]ord_{22}(1)=1[/mm] und
> dann alle weiteren potenzen der jeweiligen werte aus [mm]|\IZ[/mm]
> *_{22}| betrachtet, angefangen bei [mm]3^{k}.[/mm] wir haben jetzt
> solange potenziert, bis 1 kam, also so: [mm]3^{1}, 3^{2}, 3^{3}, 3^{4}, 3^{5}[/mm]
> usw.
> meine frage ist jetzt: reicht es nicht aus, wenn man als
> potenzen nur die werte hier nimmt:
> [mm]ord_{22}(a)\in{1,2,5,10},[/mm] also die 1,2,5,10?
Ja. Es reicht sogar aus, nur [mm] $a^2$ [/mm] und [mm] $a^5$ [/mm] modulo 22 auszurechnen: ist eins davon 1, so weisst du direkt dass [mm] $ord_{22}(a) [/mm] = 2$ bzw. [mm] $ord_{22}(a) [/mm] = 5$ ist, und wenn keins davon 1 ist, muss die Ordnung 10 sein.
Weiterhin: in einem Koerper koennen nur die Elemente [mm] $\pm [/mm] 1$ die Ordnung 1 oder 2 haben. 1 hat immer die Ordnung 1, und -1 hat Ordnung 2 wenn es nicht gleich 1 ist, und sonst Ordnung 1.
Damit brauchst du hier nur noch [mm] $a^5 \equiv [/mm] 1 [mm] \pmod{22}$ [/mm] zu testen.
> zu aufg. 2verstehe ich den schluss nicht mehr wirkl.
> wir haben zuerst alle primitivwurzeln (=PW) mod n gesucht
> und dabei herausgefunden, dass es für [mm]n\in[/mm] {16} keine
> gibt.
![[ok]](/images/smileys/ok.gif "[ok]")
> für [mm]n\in{18}[/mm] haben wir 5 als PW gefunden und um weitere zu
> finden, sind wir dann wie folgt vorgegangen (und ab hier
> verstehe ich es nicht mehr):
>
> [mm]a\equiv 5^{k}[/mm] mod 18 mit ggT(k,6)=1 und [mm]1\le k\le[/mm] 6,
> [mm]k\in\IN[/mm]
Es ist [mm] $\phi(18) [/mm] = 6$, womit die Elemente [mm] $5^0, 5^1, 5^2, 5^3, 5^4, 5^5$ [/mm] modulo 18 bereits alle Einheiten sind. Weiterhin ist [mm] $5^k$ [/mm] genau dann eine Primitivwurzel, wenn $ggT(k, [mm] \phi(18)) [/mm] = 1$ ist (und wenn [mm] $ord_{18}(5) [/mm] = [mm] \phi(18)$ [/mm] ist, was du aber schon bestimmt hast).
> => [mm]a\equiv[/mm] 5 mod 18 oder [mm]a\equiv 5^{5} \equiv[/mm] 11 mod 18
Es gibt nur zwei Zahlen in [mm] $\{ 0, 1, \dots, 5 \}$, [/mm] die teilerfremd zu 6 sind: naemlich 1 und 5. Also sind [mm] $5^1$ [/mm] und [mm] $5^5$ [/mm] modulo 18 die einzigen Primitivwurzeln modulo 18.
> => 11 ist die zweite PW mod 18.
>
> wie kommt man dadrauf? und wodran sieht man, dass 11 die
> zweite PW mod 18 ist? und wie kommt man auf das [mm]a\equiv 5^{5}\equiv[/mm]
> 11 mod 18, also die ^{5}?
Ich hoffe das ist mit dem was ich oben geschrieben hab klar.
> zum letzten teil der aufgabe 2 ist mir gerade eine
> erleuchtung gekommen ;), hoffe, dass sie stimmt;) also für
> welche [mm]b\in\IZ[/mm] gilt [mm]ord_{16}(b)=7?[/mm]
>
> ich habe folgenden ansatz gemacht:
>
> [mm]\varphi(16)=\varphi(2^{4})=8[/mm]
>
> [mm]|\IZ[/mm] *_{16}|={1,3,5,7,9,11,13,15}
>
> [mm]ord_{16}(b)|8 ord_{16}(b)={1,2,4,8}[/mm]
... womit du direkt siehst, dass kein Element modulo 16 die Ordnung 7 haben kann. Damit ist der Teil erledigt.
> [mm]\varphi(\varphi(16))=\varphi(8)=2[/mm]
>
> [mm]ord_{16}(1)=1[/mm]
>
> betrachte Potenzen von [mm]3^{k}[/mm] mit [mm]k\in\IN[/mm] ergibt
> [mm]ord_{16}(3)=4[/mm]
>
> [mm]ord_{16}(3^{k})=\bruch{4}{4,k}[/mm] =2
>
> [mm]\gdw[/mm] ggT(4,k)=2 mit [mm]k\in{2,4}[/mm]
>
> [mm]\gdw a\equiv 3^{2}\equiv[/mm] 9 mod16 oder [mm]a\equiv 3^{4}\equiv[/mm] 1
> mod 16
>
> Für a=9 oder a=1 element aus [mm]\IZ[/mm] gilt [mm]ord_{16}(b)=2[/mm]
>
> => [mm]9^{2}\equiv[/mm] 1 mod 16 oder [mm]1^{2}\equiv[/mm] 1 mod 16
Was willst du damit tun?! Was hat das mit der Aufgabe zu tun?
> verdammt, mir ist gerade aufgefallen, dass das doch falsch
> ist, oder!? :( denn ich muss ja wissen, wann [mm]ord_{16}(b)=7[/mm]
> ist und nicht 2...
Ja, genau.
Aber wann die Ordnung 7 ist hast du ja oben schon gesagt: naemlich nie.
LG Felix
|
|
|
| |
|
ja, ich glaube, ich habe es verstanden! :) danke dir! :)
und die {0,1,...5} hast du die jetzt genommen, weil wir die potenzfolge von [mm] 5^{k} [/mm] betrachten oder weil wir [mm] \varphi(18)=6 [/mm] haben und daraus dann gefolgt ist, dass 1 [mm] \le [/mm] k [mm] \le [/mm] 6 ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:28 Di 12.07.2011 | | Autor: | felixf |
Moin!
> ja, ich glaube, ich habe es verstanden! :) danke dir! :)
Bitte! :)
> und die {0,1,...5} hast du die jetzt genommen, weil wir die
> potenzfolge von [mm]5^{k}[/mm] betrachten oder weil wir
> [mm]\varphi(18)=6[/mm] haben und daraus dann gefolgt ist, dass 1 [mm]\le[/mm]
> k [mm]\le[/mm] 6 ist?
Zweiteres: weil [mm] $\varphi(18) [/mm] = 6$ ist.
LG Felix
|
|
|
|
