| Autor |
Beitrag |
    
Tiffany (T_L)
| | Veröffentlicht am Dienstag, den 29. Januar, 2002 - 18:07: | 
|
Hallöchen nocheinmal,
Mit folgender Aufgabe komme ich nicht klar:
Zeigen Sie, daß die Kongruenzgleichung
xx º 7 (mod 23)
eine Lösung besitzt und bestimmen Sie diese.
Ich fühle mich irgendwie verschaukelt. Kann man das denn mit herkömmlichen Mitteln zeigen?? Ich habe auch diverse Bücher konsultiert, konnte aber keinen Satz oder Beweis finden, der hierzu paßt.
Ist jemandem vielleicht ein Lösungsweg bekannt? |
Orion (Orion)
| | Veröffentlicht am Dienstag, den 29. Januar, 2002 - 19:20: |
|
Tiffany :
Ich schlage vor, mit dem Index zu arbeiten.
Die Zahl 5 ist eine Primitivwurzel (mod 23), d.h.
die Potenzen 5^t , 0=<t=<22 durchlaufen genau alle primen Restklassen mod 23. Zu jedem
x aus {1,...,22} gibt es also genau ein t sodass
5^t = x . t heisst Index von x bzgl. der
Primitivwurzel 5, t = ind_5 (x) (kurz : ind(x)).
Berechne einmal alle Potenzen 5^t (mod 23), aus
dieser Tabelle erhältst du dann in einfacher Weise eine Wertetabelle der Funktion ind(x).
Diese Funktion hat, wie leicht einzusehen,
die formalen Eigenschaften einer Logarithmusfunktion (man spricht daher auch vom diskreten Logarithmus), z.B.
ind(x*y) = ind(x)+ind(y) , ind(x^y)=y*ind(x).
Die Gegebene Kongruenz ist also aequivalent
zu
(*) x*ind(x) == ind(7) (mod 23)
ind(7) entnimmst du deiner Indextafel und musst
nunmehr nur noch die Produkte x*ind(x) überprüfen, ob (*) erfüllt ist.
mfg
Orion |
Orion (Orion)
| | Veröffentlicht am Dienstag, den 29. Januar, 2002 - 19:23: |
|
Tiffany :
Ich schlage vor, mit dem Index zu arbeiten.
Die Zahl 5 ist eine Primitivwurzel (mod 23), d.h.
die Potenzen 5^t , 0=<t=<22 durchlaufen genau alle primen Restklassen mod 23. Zu jedem
x aus {1,...,22} gibt es also genau ein t sodass
5^t = x . t heisst Index von x bzgl. der
Primitivwurzel 5, t = ind_5 (x) (kurz : ind(x)).
Berechne einmal alle Potenzen 5^t (mod 23), aus
dieser Tabelle erhältst du dann in einfacher Weise eine Wertetabelle der Funktion ind(x).
Diese Funktion hat, wie leicht einzusehen,
die formalen Eigenschaften einer Logarithmusfunktion (man spricht daher auch vom diskreten Logarithmus), z.B.
ind(x*y) = ind(x)+ind(y) , ind(x^y)=y*ind(x).
Die Gegebene Kongruenz ist also aequivalent
zu
(*) x*ind(x) == ind(7) (mod 23)
ind(7) entnimmst du deiner Indextafel und musst
nunmehr nur noch die Produkte x*ind(x) überprüfen, ob (*) erfüllt ist.
mfg
Orion |
Orion (Orion)
| | Veröffentlicht am Mittwoch, den 30. Januar, 2002 - 17:25: |
|
Sorry, da ist mir noch ein sinnentstellender
Schreibfehler unterlaufen : (*) muss natürlich
lauten
x*ind(x) == ind(7) (mod 22)
mfg
Orion |
Tiffany (T_L)
| | Veröffentlicht am Mittwoch, den 30. Januar, 2002 - 21:10: |
|
Hallo Orion!
Ich hab mich nochmal schlau gemacht, den Index heranzuziehen ist wirklich ein interessanter Ansatz. Das ist natürlich schön, daß man mit 5 eine einfache Primitivwurzel zur Verfügung hat. Im folgenden die Potenzen von 5 in aufsteigender Reihenfolge (beginnend mit t=0):
1,5,2,10,4,20,8,17,16,11,9,22,18,21,13,19,3,15,6,7,12,14.
Die Umkehrabbildung 5t ® t ist gerade der Index. Man erhält somit folgende Werte für den Index (beginnend bei x=1):
0,2,16,4,1,18,19,6,10,3,9,20,14,21,17,8,7,12,15,5,13,11.
Ausgehend von deiner Idee ergibt sich dann ja
xx º 7 (mod 23),
(5t)x º 7 (mod 23),
5t*x º 7 (mod 23),
t*x º ind5(7) (mod 23),
Aus der Übersicht von oben entnimmt man ind5(7) º 19 (mod 23), also ist
x*ind5(x) º 19 (mod 23)
zu lösen (oder?). Das Modul müßte also immer noch 23 sein.
Ich habe bei der Gleichung aber sämtliche 22 Werte durchgetestet und keine Lösung gefunden (auch mit Probe nicht!). Ist die obige Gleichung also falsch? Ich glaube der Haken an der ganzen Sache ist doch, daß nicht unbedingt 1 £ x £ 22 gelten muß (das war doch Voraussetzung?). Kannst du das mal prüfen?
MfG Tiffany |
Orion (Orion)
| | Veröffentlicht am Mittwoch, den 30. Januar, 2002 - 22:09: |
|
Hallo:
Ja, deine Indextafel ist völlig korrekt. Man muss
allerdings allgemein mit den ind-Werten nicht
mod m, sondern mod phi(m), phi= Eulerfunktion,
rechnen. Wenn m=p Primzahl ist, also mod(p-1).
Für die Produkte x*ind(x) (mod 22) finde ich
der Reihe nach die Werte (rechne nach !)
0,4,4,16,5,20,1,4,2,8,11,20,6,8,13,18,9,18,21,12,9.
Als Lösungen von x^x == a (mod 23) finde ich damit z.B:
a=2 : x == 9 (mod(23)
a=4 : x == 2,3,8 (mod 23)
a=6 : x == 18 (mod 23)
was man alles leicht nachprüft. In obiger Tabelle
kommt 19 = ind(7) nicht vor, also gibt es für a = 7 keine Lösung, im Gegensatz zur Behauptung des
Aufgabenstellers (und falls ich richtig gerechnet habe...).
mfg
Orion |
Kay Schönberger (Kay_S)
| | Veröffentlicht am Donnerstag, den 31. Januar, 2002 - 13:40: |
|
Hallo Orion & Tiffany
So dumm war der Autor gar nicht!
Ihr macht euch das nämlich leider etwas zu einfach. Ihr habt nur gezeigt, daß für 1 £ x £ 22 keine Lösung existiert. Im Gegensatz zum reinen diskreten Logarithmus (wo das Intervall genügen würde) taucht hier noch zusätzlich ein variabler Faktor auf (nämlich x), mal ganz davon abgesehen, daß der Index selbst ja mehrdeutig ist.
Nachfolgend beweise ich, daß x = 263 eine Lösung der Gleichung ist:
263 º 10 (mod 23)
« 2632 º 102 º 8 (mod 23)
« 2634 º 82 º 18 (mod 23)
« 2638 º 182 º 2 (mod 23)
« 26364 º 28 º 3 (mod 23)
« 263256 º 34 º 12 (mod 23)
« 263260 º 263256 * 2634 º 12 * 18 º 9 (mod 23)
« 263262 º 263260 * 2632 º 9 * 8 º 3 (mod 23)
« 263263 º 3 * 263 º 7 (mod 23)
Peng!
Kay S. |
Orion (Orion)
| | Veröffentlicht am Donnerstag, den 31. Januar, 2002 - 15:51: |
|
Hallo Kay :
ok, akzeptiert. Verrätst du uns noch, wie du
auf 263 gekommen bist ?
mfg
Orion |
Kay Schönberger (Kay_S)
| | Veröffentlicht am Freitag, den 01. Februar, 2002 - 12:19: |
|
Orion,
Ich habe einfach meinen PC rechnen lassen. Ich weiß jedenfalls nicht, wie man anders auf die Lösung kommen könnte (beim Index ist es ja ähnlich).
Das würde ich mal gerne den Aufgabensteller fragen, zumal uns doch wohl alle interessiert, wie er sich denn das gedacht hat!
Übrigens ist 263 die kleinste mögliche Lösung. Ich denke es lohnt sich, solche oder ähnliche Aufgaben einmal näher zu untersuchen.
Kay S. |
Carmichael (Carmichael)
| | Veröffentlicht am Freitag, den 01. Februar, 2002 - 13:03: |
|
Hi Mathematikfreunde!
Ich will mich auch mal an dieser interessanten Fragestellung beteiligen.
Wie bereits bemerkt wird x^x mod p erst nach p(p-1) "auffällig" periodisch.
Man findet so schnell eine Formel, wie man y (beliebig aus Z/pZ) als x^x darstellen kann.
Es gilt:
y = (1+(p-1)(p+1-y))^(1+(p-1)(p+1-y)) (mod p);
(einfacher trick mit kleinem fermat)
angewendet auf angegebenes Beispiel:
7 = (1+(23-1)(23+1-7))^(1+(23-1)(23+1-7)) =
= 375^375 (mod 23);
Man sogar phi(p-1) x^x-"wurzeln" von y angeben.
denn weiter gilt:
sei ggT(r,p-1) = 1:
y = (r + (p-1)(p+r-y^(r^( phi(p-1)-1)) ) ) ^ (r + (p-1)(p+r-y^(r^( phi(p-1)-1)) ) ) (mod p);
MfG |
|
