effiziente Berechnung der Ordnung in Restklassengruppen

16/02/2008 - 14:24 von Thomas Plehn | Report spam
Hallo,

im folgenden bezeichne ord_b(a) die Ordnung des Elementes a modulo b.
d.h. min{i|a^i=1(mod b)}

bekannt dazu ist mir folgende Regel:
ord_b(a_1*a_2) = KgV(ord_b(a_1), ord_b(a_2))

gibt es eine àhnliche Regel zur Aufspaltung der Faktoren auch für
ord_{b_1*b_2}(a)?

ich habe schon überlegt, dass ja
a^i=1(mod b_1*b_2)
gelten muss, also
b_1*b_2 | a^i - 1
was genau dann der Fall ist, wenn
b_1 | a^i - 1 und b_2 | a_i - 1 und ggT(b_1,b_2)=1
umgeschrieben also:
a^i=1(mod b_1) und a^i=1(mod b_2)
die Lösungsmengen sind jeweils
{k*ord_{b_1}(a)|k\in\N} und {k*ord_{b_2}(a)|k\in\N}
das kleinste Schnittelement also analog zu oben
KgV(ord_{b_1}(a), ord_{b_2}(a))
richtig?

zu der bekannten Regel habe ich mir überlegt:
a_1^i * a_2^i = 1(mod b)
genau dann wenn
a_1^i = 1(mod b) und a_2^i = 1(mod b)
die Lösungsmengen sind analog zu oben
{k*ord_b(a_1)|k\in\N} und {k*ord_b(a_2)|k\in\N}
kleinstes Schnittelement ist also wieder
KgV(ord_b(a_1), ord_b(a_2))

irgendwie erstaunlich, alles so richtig?
das würde nàmlich bedeuten, das man mit Tabellen der Ordnung von
Primzahlen modulo Primzahlen auskommen würde und alles daraus berechnen
könnte. richtig?
 

Lesen sie die antworten

#1 Thomas Plehn
18/02/2008 - 13:18 | Warnen spam
Thomas Plehn schrieb:


im folgenden bezeichne ord_b(a) die Ordnung des Elementes a modulo b.
d.h. min{i|a^i=1(mod b)}

bekannt dazu ist mir folgende Regel:
ord_b(a_1*a_2) = KgV(ord_b(a_1), ord_b(a_2))

gibt es eine àhnliche Regel zur Aufspaltung der Faktoren auch für
ord_{b_1*b_2}(a)?




Das ist eine ernsthafte Frage. Ich bin mir nicht sicher, ob meine
Überlegungen stimmen. Bitte um Rückmeldungen.

Ähnliche fragen