2^r = 1 (mod 37) - Für welche r gilt diese Aussage?

03.06.2010, 16:07

PeterH

2^r = 1 (mod 37) - Für welche r gilt diese Aussage?

Meine Frage:
Hallo alle miteinander,
Ich habe die Frage, für welche Werte für r folgendes gilt:
$\begin{eqnarray*} 2^{r} = 1 \left(mod 37\right) \end{eqnarray*}$
Gibt es irgendeinen allgemeinen Ansatz, mit dem man Probleme der Form
$\begin{eqnarray*} 2^{r} = 1 \left(mod x\right) \end{eqnarray*}$ lösen kann?
Ich würde mich sehr über eine Antwort freuen.

Mfg PeterH

Meine Ideen:

03.06.2010, 16:11

lgrizu

Auf diesen Beitrag antworten »

RE: 2^r = 1 (mod 37) - Für welche r gilt diese Aussage?
da 37 ne primzahl ist kann man hier den kleinen fermat gebrauchen:

a^p=a mod p also a^(p-1)=1 mod p. dein a ist die zwei, dein p ist die 37 Augenzwinkern

03.06.2010, 16:31

PeterH

Auf diesen Beitrag antworten »

RE: 2^r = 1 (mod 37) - Für welche r gilt diese Aussage?
Vielen Dank für die Antwort! Für das Beispiel funktioniert es wunderbar. Doch ich habe mal eine Frage: Wenn ich a=2 und p=7 habe, ist die Potenz r nach Fermat sechs, wobei doch schon drei als Ergebnis mod 7 eins ergibt. Heißt das, dass Fermat einem zwar immer ein passendes Ergebnis gibt, dass dies jedoch nicht das kleinste sein muss? Wenn ja: Gibt es eine Möglichkeit das kleinste herauszufinden?

03.06.2010, 17:22

lgrizu

Auf diesen Beitrag antworten »

RE: 2^r = 1 (mod 37) - Für welche r gilt diese Aussage?
es muss nicht das kleinste sein, aber es passt immer....
es ist nach euler eine folgerung von fermat (folgt direkt aus der 3. binomischen formel und dem kleinen fermat):

$\begin{eqnarray*} a^{\frac{p-1}{2}}=\pm 1 mod~p \end{eqnarray*}$

kannst auch mal bei wiki gucken, ich denke, da steht noch was zu fermat, dann muss ich das nicht alles hinschreiben..... Augenzwinkern

03.06.2010, 17:27

Auf diesen Beitrag antworten »

Zitat:

Original von PeterH
Wenn ja: Gibt es eine Möglichkeit das kleinste herauszufinden?

Die gesuchte Ordnung von $\begin{eqnarray*} a \end{eqnarray*}$ ist auf alle Fälle ein Teiler von $\begin{eqnarray*} (p-1) \end{eqnarray*}$ , das reduziert zumindest etwas die in Frage kommenden Kandidaten. Augenzwinkern

Für beliebige $\begin{eqnarray*} x \end{eqnarray*}$ (also nicht nur Primzahlen) und dazu teilerfremde $\begin{eqnarray*} a \end{eqnarray*}$ lautet die Antwort natürlich $\begin{eqnarray*} \operatorname{ord}(a) \mid \varphi(x) \end{eqnarray*}$ .

EDIT: Und bevor Mystic sich wieder beschwert: Es gilt sogar $\begin{eqnarray*} \operatorname{ord}(a) \mid \lambda(x) \end{eqnarray*}$ , wobei $\begin{eqnarray*} \lambda(x) \end{eqnarray*}$ die Carmichael-Funktion darstellt. Augenzwinkern

03.06.2010, 17:58

Mystic

Auf diesen Beitrag antworten »

Ja, tatsächlich ist das einzige "echte" Problem die Bestimmung der Primfaktoren von r= p-1, zumindestens falls p "groß" ist, der Rest ist dann "plain sailing"...Man muss einfach dann für jeden Primfaktor q von r prüfen, ob gilt

$\begin{eqnarray*} a^{r/q} \equiv 1\mod p \end{eqnarray*}$

und zutreffendenfalls die Ersetzung $\begin{eqnarray*} r \leftarrow r/q \end{eqnarray*}$ vornehmen... Wenn eine "Verkleinerung" von r auf diesem Wege nicht mehr möglich ist, dann ist das aktuelle r die Ordnung von a mod p...

Edit: Ja Arthur, freut mich zu sehen, dass mein Lamentieren über die "suboptimale" Verwendung von $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ statt $\begin{eqnarray*} \lambda(n) \end{eqnarray*}$ doch langsam Früchte hier trägt... Augenzwinkern

03.06.2010, 20:12

PeterH

Auf diesen Beitrag antworten »

Danke sehr!

Neue Frage »

Antworten »

2^r = 1 (mod 37) - Für welche r gilt diese Aussage?

Verwandte Themen