| Autor |
Beitrag |
    
Kay Schönberger (Kay_S)
| | Veröffentlicht am Samstag, den 26. Januar, 2002 - 14:25: | 
|
Hallo,
Gegeben Sei eine Kongruenzgleichung der Form
ax º b (mod p)
mit vorgegebenen a,b, Primzahl p und einer Unbekannten x.
Ist jemandem vielleicht bekannt, welche Kriterien die Primzahl p erfüllen muß, damit die vorgelegte Gleichung eine Lösung in x besitzt?
Bin für jeden Ansatz dankbar.
Kay S. |
Orion (Orion)
| | Veröffentlicht am Sonntag, den 27. Januar, 2002 - 08:15: |
|
Kay :
Kurzer Hinweis : Dies hat zu tun mit dem Begriff
Primitivwurzel :
g heisst Primitivwurzel mod m, wenn die Potenzen
1,g,g^2,...,g^(phi(m)-1) ; phi = Eulerfunktion
ein volles reduziertes Restsystem mod m bilden.
Wenn (a,m) = 1, so gibt es ein eindeutig bestimmtes k mit a == g^k (mod m), und man
definiert k =: ind_g (a) . ind_g entspricht dem
Logarithmus. Falls m Primitivwurzeln g besitzt, so gilt
a^x == b (mod m) <==>
x*ind_g (a) == ind_g (b) (mod m)
Nicht für jedes m gibt es Primitivwurzeln (z.B.:
m = 8). Hingegen gilt der
Satz: Jede Primzahl p besitzt phi(p-1) Primitivwurzeln.
Der Beweis ist nicht ganz trivial (s.z.B.:
Remmert/Ullrich : Elementare Zahlentheorie,
Birkhaeuser 1987)
mfg
Orion |
|
