Finde alle Lösungen zu x^3≡ 5 mod 13

Question

Da ich morgen Klausur schreibe, wiederhole ich nochmal ein paar alte Aufgaben. In unserer Probeklausur hatten wir folgende Aufgabe:

Finde alle Lösungen zu x³≡ 5 mod 13.

Unser Prof hat die Aufgabe später zwar angesprochen, aber ich blicke da irgendwie nicht durch. Er hat nur folgende Tabelle gemacht:

x	x³
1	1
2	8
3	27
4	64
5	125
-5	-125

Das sind aber nicht die Lösungen.

Kann mir einer sagen, man bei so einer Aufgabe vorgehen muss?

Comments

Ich kann leider selber damit nicht viel anfangen, habe aber fast die gleiche Aufgabe hier gefunden:

http://www.mi.uni-koeln.de:8918/Klausur-Loesungen.pdf

(Aufgabe 5)

 

Answer 1

Wenn der eine ganze Tabelle hinschreibt, heisst das wohl, dass ihr einfach ausprobieren müsst.

x^3 = 5 + k*13

x^3 - 5 = k*13

(x^3 - 5) / 13 = k   ganzzahlig

und jetzt einfach alle Zahlen von x= 0 bis 12 durchprobieren und die Äquivalenzklassen dieser Resultate hinschreiben.

Sehe gerade, dass (-125 - 5) = -130 aufgeht. Könnte es sein, dass die Äquivalenzklasse von -5 also [-5 ± 13] d.h. [8] die einzige Lösung ist, da 13 eine Primzahl ist? Ich weiss, dass nicht!

Wenn du sicher sein willst, dass du alles hast, musst du wohl noch weiterprobieren.

Wen man immer gleich +x^3 und -x^3 ansieht, ist man bei 6^3, spätestens 7^3 fertig.