x^3 kongruent 1 mod 19?

Question

Ich habe Probleme mir der Lösung folgender Gleichung:  x^3 ≡ 1 mod 19

Laut Vorlesung soll man x=2^y   setzen

Ich bin dann soweit:

2^3y  ≡ 1 mod 19

⇔ 2^3y    ≡ -2⁹  mod 19

⇔ 2^3y-9  ≡ -2 mod 19

⇔ 2^3y-9  ≡ 17 mod 19

Jetzt soll man etwas mit den Exponent machen ? Und genau diesen Schritt verstehe ich nicht..

Comments

Oh daran habe ich gar nicht gedacht. Schon mal Danke. Aber gibt es keine andere Methode? Bei höheren Potenzen ist dieser Lösungsweg doch nicht mehr so schön oder? Wie würde ich bei x⁶ ≡ 10 mod 23 vorgehen?

---

@Nic2431: Wie genau kommst du in der zweiten Zeile auf -2⁹   ? 

V.a. das Minus?

Ohne ein Minus könnte man vielleicht (?)  in einer Zeile wie hier:  

 2^3y    ≡ -2⁹  mod 19 

die Exponenten vergleichen (Gleichsetzen?) 

---

@Lu Gute Frage. Jetzt wo ich es mir noch mal ansehe, merke ich, dass da Mist steht.

---

2^3y  ≡ 1 mod 19

2^3y  ≡ 2^0 mod 19

Exponentenvergleich: 3y = 0 ==> y = 0 ==> x = 2^0 = 1 . Scheint zu klappen. Aber das ist nur die erste und offensichtliche Lösung.  

---

ALso -2⁹  ist doch richtig oder nicht? x³ ≡ 1 mod 19 ⇔ x³ ≡ -512 = -2^9 mod 19 oder übersehe ich etwas?

In der Vorlesung hatten wir folgendes Beispiel

x⁴  ≡ 8 mod 11 ⇔ 2^4y- ⇔ 2³ mod 11 ⇔ 2^4y-3 ≡ 2 mod 11 ⇔ 10 teilt 4y-3 ⇔ 4y-3 ≡ 0 mod 11 ⇔ 4y ≡ 3 mod 11

2 teilt 4, 2 teilt 10, aber 2 teilt nicht 3 ⇒ es ex keine Lösung. Aber daraus werde ich nicht richtig schlau.

Answer 1

Alternative: x³ ≡ 1 mod 19
⇔ x³ - 1 ≡ 0 mod 19
⇔ (x - 1)·(x² + x + 1) ≡ 0 mod 19
⇔ (x - 1)·(x² - 18x + 1) ≡ 0 mod 19
⇔ (x - 1)·((x - 9)² - 9² + 1) ≡ 0 mod 19
⇔ (x - 1)·((x - 9)² - 2²) ≡ 0 mod 19
⇔ (x - 1)·(x - 7)·(x - 11) ≡ 0 mod 19.

Comments

Vielleicht so: 2^3y ≡ 1 mod 19
⇔ 2^3y ≡ 2¹⁸ mod 19
⇔ 18 teilt 3y
(1)  3y = 0·18 ⇔ y = 0 ⇒ x = 1
(2)  3y = 1·18 ⇔ y = 6 ⇒ x = 7
(3)  3y = 2·18 ⇔ y = 12 ⇒ x = 11.

---

Oh man. Das ist ja eigentlich ganz einfach. Also brauch ich immer eine Potenz mit der Basis 2 auf der rechten Seite um die Exponenten zu vergleichen?