Question

Bestimmen Sie alle x ∈ Z42, die die Gleichung 13 · x ≡ 40⁸ (mod 42) erfüllen.

Mir geht es dabei nicht direkt um die Lösung der Gleichung, sondern viel mehr darum, wie man die 40⁸ mod42 am cleversten ausrechnet. Kann mir dabei jemand helfen?

Answer 1

Also erstmal gilt $40 \equiv -2 \mod (42)$, die Kongruenz vereinfacht sich also zu $$13x \equiv (-2)^8 \mod (42)$$

(-2)^8 kann man im Kopf ausrechnen oder weiß es auswendig: 256. Die Vielfachen von 42 sind 42, 84, 126, 168, 210, 252. also ist $256 \equiv 4 \mod 42$. Man erhält

$$13x \equiv 4 \mod (42)$$

Und jetzt muss man nur noch das multiplikativ Inverse von 13 modulo 42 finden, das geht auch da ggT(13,42) = 1. Das macht man mit dem erweiterten Euklidischen Algorithmus

$$\operatorname{ggT}(13,42) = 1 = 13\cdot 13 - 4 \cdot 42$$

also ist das multiplikativ Inverse von 13 gerade 13 selbst. Wir multiplizieren mit 13

$$x\equiv 13^2x \equiv 4\cdot 13 \equiv 52 \equiv 10 \mod (42)$$

Comments

Vielen Dank für die ausführliche Lösung! :)

---

Ich habe mal eine kurze Frage zur letzten Zeile. 

Die Zeile  13x ≡ 4 mod(42) wird mit der Inversen von 13 multipliziert. In diesem Fall ist das wieder 13, wie löst sich dann aber die 13² x ≡ 4 mod(42) auf?

Wird das "ausgerechnet" 169 mod 42 ≡ 1 mod 42 oder kürzt die Inverse von 13 die 13 direkt weg? 

---

Beides ist richtig.

---

13 ist invers zu 13 bedeutet $13\cdot 13 \equiv 1 \mod 42$

Wenn du die Kongruenz 13x≡4 mit 13 durch multiplizierst steht links direkt x und rechts 13*4.

13² x ≡ 4 mod(42)

Da steht dann 13² x ≡ 13*4 mod(42), du musst auf beiden Seiten multiplizieren, das ist wie bei Gleichungen

---

Ok, vielen Dank!