Mult. Ordnung der 3 mod 2^n < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:36 Fr 02.11.2012 | | Autor: | icarus89 |
| Aufgabe | Zeigen Sie, dass die multiplikative Ordnung der 3 modulo [mm] 2^{n} [/mm] maximal ist, das heißt:
ord(3 mod [mm] 2^{n} [/mm] ) = [mm] max_{x \in (\IZ/ 2^{n}\IZ)^{\*}} [/mm] ord(x) |
Heyho!
Meine einzige Idee, wie ich das zeigen könnte, war der binomische Lehrsatz. Die Inversen sind ja gerade alle ungeraden Zahlen, also 3+2 k.
Ich wollte jetzt zeigen, dass mit [mm] 3^{m} \equiv [/mm] 1 mod [mm] 2^{n} [/mm] auch
(3 + 2 k ){m} [mm] \equiv [/mm] 1 mod [mm] 2^{n} [/mm]
Aber der binomische Lehrsatz hilft einem da nicht wirklich, denn es ist
( 3 + 2k [mm] )^{m} [/mm] = [mm] 3^{m} [/mm] + [mm] \sum_{i=1}^{m-1} \binom{m}{i} 3^{m-i} (2k)^{i}
[/mm]
und ich sehe nicht, warum der Rest durch [mm] 2^{n} [/mm] teilbar sein sollte.
Wenn das tatsächlich eine Sackgasse ist, wie kann man sonst an die Sache rangehen?
|
|
| |
|
moin,
Ich würde dir empfehlen [mm] $3^m [/mm] = [mm] (2+1)^m [/mm] = [mm] \summe_{k=0}^m [/mm] {m [mm] \choose [/mm] k} [mm] 2^k$ [/mm] zu schreiben.
Damit ist [mm] $3^m \equiv [/mm] 1$ [mm] mod($2^n$) $\gdw$ $2^n \mid \summe_{k=1}^m [/mm] {m [mm] \choose [/mm] k} [mm] 2^k$ [/mm] und du hast es zumindest nur noch mit Zweien zu tun.
Da ich nicht sicher weiß, ob man damit bis zur kompletten Lösung kommt, lasse ich die Frage mal halb offen.
lg
Schadow
|
|
|
| |
|
Hallo icarus,
ich würde für [mm] n\ge{3} [/mm] zwei Dinge zeigen:
1) [mm] 3^{(2^{n-3})}\not\equiv 1\mod{2^n}
[/mm]
2) [mm] (2k+1)^{(2^{n-2})}\equiv 1\mod{2^n}
[/mm]
Wenn Du beides zeigen kannst, ist die Behauptung damit bewiesen.
Achte oben genau auf die Exponenten.
Die Fälle n=1 und n=2 sind dann noch zu Fuß zu erledigen, aber das ist ja ausnehmend unproblematisch.
Grüße
reverend
|
|
|
| |
|
> Hallo icarus,
>
> ich würde für [mm]n\ge{3}[/mm] zwei Dinge zeigen:
>
> 1) [mm]3^{(2^{n-3})}\not\equiv 1\mod{2^n}[/mm]
>
Also ich habe für n>3 herausgefunden, dass [mm] 3^{(2^{n-3})} \equiv 2^{n-1} [/mm] + 1 [mm] \mod{2^{n}}
[/mm]
(aber nur durch ein paar Beispiele, wie ich das beweise weiß ich nicht...)
Wenn ich das für n annehme, dann krieg ich heraus, dass
[mm] 3^{(2^{n-2})} \equiv [/mm] 1 mod [mm] 2^{n} [/mm]
also [mm] 3^{(2^{n-2})} \equiv [/mm] 1 mod [mm] 2^{n+1} [/mm]
oder [mm] 3^{(2^{n-2})} \equiv 2^{n} [/mm] + 1 mod [mm] 2^{n+1} [/mm]
das hilft irgendwie überhaupt nicht dabei zu zeigen, dass es nicht kongruent zur 1 ist, sondern zeigt nur, dass die Behauptung wahr ist, wenn es nicht kongruent zur 1 ist. -.-
Also muss man anders an die Sache rangehen. Kann man irgendwie einen Widerspruch folgern, wenn man annimmt, dass das Ding kongruent zu 1 ist?
> 2) [mm](2k+1)^{(2^{n-2})}\equiv 1\mod{2^n}[/mm]
>
Beim zweiten wäre zu zeigen, dass
[mm] \sum_{i=0}^{n-1} \binom{2^{n-2}}{i} [/mm] (2 k [mm] )^{i} \equiv [/mm] 1 [mm] \mod{2^{n}}
[/mm]
Der Rest fällt ja schonmal weg und auch hier sind dritter und fünfter Summand durch [mm] 2^{n} [/mm] teilbar. Warum das ganze Ding (ab i=1) durch [mm] 2^{n} [/mm] teilbar ist, sehe ich aber nicht.
Okay, lass ich das...
Es reicht doch hier zu zeigen, dass die Einheitengruppe für n>2 nicht zyklisch ist, oder? Dann kann ja kein Element "volle Ordnung" haben und eine Ordnung kleiner ist ja gerade [mm] 2^{n-2}. [/mm]
Dann bleibt nur noch der Teil mit der 3...
> Wenn Du beides zeigen kannst, ist die Behauptung damit
> bewiesen.
> Achte oben genau auf die Exponenten.
>
> Die Fälle n=1 und n=2 sind dann noch zu Fuß zu erledigen,
> aber das ist ja ausnehmend unproblematisch.
>
> Grüße
> reverend
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Do 08.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
