[Zahlentheorie] Modulare Inverse

Hi,

wenn ich folgende Gleichung gegeben habe:

(a*x)mod99 = 1

und die Frage lautet: Für wieviele a in Z₉₉ ist diese Gleichung erfüllt ?
Dann existiert die die modulare Inverse ja nur, wenn gilt ggT(a,99)=1. Dies ist genau für Φ(99) (eulerische Funktion) Zahlen erfüllt.

Nun lautet die Gleichung aber:

(a*x)mod99 = 3

Daher gehe ich auf =1 runter:

(a/3*x)mod33 = 1

Die gilt also nur wenn ggT(a/3,33)=1 ist. Φ(33) ist 20. Ich weiß nun aber nicht ob a/3 auf diesen 20 Zahlen sitzt. Man könnte die Menge a/3 aufschreiben und die 20 Teilfremden ebenso und die Mächtigkeit der Schnittmenge wäre dann die gesuchte Lösung.

Sind diese Überlegung richtig ? Und wie kann ich die zweite Gleichung elegant und einfach lösen ?

otze

Du darfst gar nicht durch durch 3 teilen, da 3 in Z99 keine Inverse hat(ggt(3,99)=3!=1)

//edit bzw nicht in Z33

Hmm, stimmt und wie löse ich dann

(a*x)mod99 = 3

am einfachsten ?

Ben04

Eine Lösung findet man mit dem Satz von Euler:

a*x ≡ b (mod c)

Der Satz von Euler sagt, dass

a^(φ(c))≡ 1 (mod c)

Damit können wir schnell eine Lösung basteln

x = a^(φ(c)-1)*b

denn

a*a^(φ(c)-1)*b ≡ a^(φ(c)) * b ≡ b (mod c)

Super danke. Nur macht mein Taschrenrechner bei großem φ(c) schnell schlapp. Ich könnte zwar die Potenz zerstückeln und dann jeweils modulo reduzieren, aber das wäre auch zuviel Tipparbeit.

Habe inzwischen aber noch ne andere Lösungmethode in Erfahrung bringen können:

(1) a*x ≡ 3 (mod c)
Die modulare Inverse(a^-1) von a in Zc bestimmen und (1) damit multiplizieren:

a*a^-1 ≡ 1 (mod c) -- mit euklid bestimmen

a*x*a^-1 ≡ 3*a^-1 (mod c)

x ≡ 3*a^-1 (mod c)

Ist das richtig ?

otze

ja, aber das ändert an deinem Grundproblem nichts. du musst immer noch alle möglichen a^-1 ausprobieren.

otze schrieb:

ja, aber das ändert an deinem Grundproblem nichts. du musst immer noch alle möglichen a^-1 ausprobieren.

Laut der vorherigen Methode, habe ich ja nur eine Lösung, wenn ich a^-1 bestimmen kann. Diese exisistiert ja nur in Z99 für ggt(a,99)=1, also für alle teilerfremden von 99. Dies wäre dann genau für phi(99) Zahlen der Fall. (?)