2^m mod 23 = 1

01.02.2006, 00:52

HomerJay

2^m mod 23 = 1

Hallo,

ich habe eine frage zu folgendem aufgabentyp (es geht um BCH-codes):

$\begin{eqnarray*} 2^{m} mod 23 = 1 \end{eqnarray*}$

durch probieren komme ich auf m=11, weil 2^11 = 2048 und das ist 1 in mod 23.

nun meine frage: gibt es auch eine möglichkeit, solche aufgaben ohne "probieren" zu lösen...ich denke mal schon und wäre sehr dankbar, wenn mir das jemand erklären könnte.

Vielen Dank
Oli

01.02.2006, 10:07

Auf diesen Beitrag antworten »

Die prime Restklassengruppe modulo $\begin{eqnarray*} m \end{eqnarray*}$ hat genau $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ Elemente (siehe auch Satz von Fermat-Euler). Die Ordnung $\begin{eqnarray*} o(a) \end{eqnarray*}$ eines jeden Gruppenelements $\begin{eqnarray*} a \end{eqnarray*}$ , das ist hier die kleinste positive ganze Zahl mit der Eigenschaft $\begin{eqnarray*} a^{o(a)} \equiv 1\mod m \end{eqnarray*}$ , muss ein Teiler dieser Gruppenordnung sein.

Ist $\begin{eqnarray*} m \end{eqnarray*}$ Primzahl, so gilt $\begin{eqnarray*} \varphi(m)=m-1 \end{eqnarray*}$ , im vorliegenden Fall $\begin{eqnarray*} \varphi(23)=22 \end{eqnarray*}$ . Also gilt für die Ordnung der 2 auf alle Fälle $\begin{eqnarray*} o(2)|22 \end{eqnarray*}$ . Zum Probieren bleiben somit nur noch die Varianten 2 und 11 zu untersuchen (1 scheidet natürlich aus), im vorliegenden Fall ist es letztendlich $\begin{eqnarray*} o(2)=11 \end{eqnarray*}$ .

01.02.2006, 12:45

HomerJay

Auf diesen Beitrag antworten »

vielen dank!

01.02.2006, 13:54

HomerJay

Auf diesen Beitrag antworten »

ok, ich hab da scheinbar doch noch ein kleines problem...andere aufgabe, selbes schema:

$\begin{eqnarray*} 2^{m} mod 21 = 1 \end{eqnarray*}$

lösung ist hier m=6 (wieder durch probieren)

laut deiner erklärung müsste m aber teiler von 21 sein...also wären nur 3 und 7 zu untersuchen.

wo ist mein denkfehler?

danke
Oli

01.02.2006, 14:02

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Die prime Restklassengruppe modulo $\begin{eqnarray*} m \end{eqnarray*}$ hat genau $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ Elemente (siehe auch Satz von Fermat-Euler). Die Ordnung $\begin{eqnarray*} o(a) \end{eqnarray*}$ eines jeden Gruppenelements $\begin{eqnarray*} a \end{eqnarray*}$ , das ist hier die kleinste positive ganze Zahl mit der Eigenschaft $\begin{eqnarray*} a^{o(a)} \equiv 1\mod m \end{eqnarray*}$ , muss ein Teiler dieser Gruppenordnung sein.

Nicht Teiler von m, sondern von $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ .

Beachte auch, dass m hier nicht prim ist und somit Arthurs 2. Absatz nicht gilt.

01.02.2006, 15:20

Auf diesen Beitrag antworten »

Konkret heißt das: $\begin{eqnarray*} \varphi(21)=\varphi(3\cdot 7)=2\cdot 6=12 \end{eqnarray*}$ , also $\begin{eqnarray*} o(2)|12 \end{eqnarray*}$ .

01.02.2006, 17:32

HomerJay

Auf diesen Beitrag antworten »

ok, danke...nu hab ichs verstanden

01.02.2006, 17:52

HomerJay

Auf diesen Beitrag antworten »

mmmh...noch eine kleine frage Augenzwinkern

du hast die 21 ja recht praktisch in ihre faktoren zerlegt und dann mit deren funktzionswerten bezüglich der phi-funktion weitergerechnet. das schaut sehr praktisch aus, aber leider kann man es wohl nicht immer anwenden ?!?

bsp: $\begin{eqnarray*} 2^{m} mod 24 = 1 \end{eqnarray*}$

ergebnis ist mir hier noch nicht bekannt...aber phi(24) müsste doch 8 sein...somit wären m=4 und m=2 zu untersuchen...das haut ja nich so ganz hin

danke
Oli

PS.: sorry für meine doppelposts, in zukunft rechne ich erst und schreibe dann, dass ich es verstanden habe Augenzwinkern

02.02.2006, 09:00

Denjell

Auf diesen Beitrag antworten »

ne gerade zahl geteilt durch ne gerade Zahl kann doch sowieso nie den Rest 1 haben oder irr ich mich?

02.02.2006, 10:04

Auf diesen Beitrag antworten »

Vollkommen richtig, Denjell.

Wenn man Fermat-Euler $\begin{eqnarray*} a^{\varphi(m)}\equiv 1\mod m \end{eqnarray*}$ anwenden will, muss man natürlich die Voraussetzungen beachten: Und die lauten hier, dass $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ teilerfremd sein müssen. Das ist bei $\begin{eqnarray*} a=2 \end{eqnarray*}$ und $\begin{eqnarray*} m=24 \end{eqnarray*}$ nicht erfüllt!

Neue Frage »

Antworten »

2^m mod 23 = 1

Verwandte Themen