Kongruenz Modulo x bestimmen

Question

ich habe folgende Aufgabe bekommen.

ich soll diese Gleichung lösen:

x = 5 mod 9

wie mache ich sowas ?

Gruß

EDIT: Aus Kommentar " Ach bin in der Zeile verrutscht. 

Es geht um diese Gleichung

x = 2^578347903 mod 5 "

Comments

Hi, das kann ja wohl nicht ganze Aufgabe sein, denn die Gleichung ist ja schon gelöst. Also bitte die fehlenden Details nachreichen!

---

Ach bin in der Zeile verrutscht.

Es geht um diese Gleichung

x = 2^{578347903} mod 5

Answer 1

https://www.wolframalpha.com/input/?i=x+%3D+5+mod+9++

Comments

Schon klar. Mit einem Lösungssystem geht das. Aber möchte einen Algorithmus oder so dafür ?

Answer 2

Na ja, nutze zum Beispiel 2^4 = 16 ≡ 1 mod 5 und verkleinere mal den Exponenten!

Comments

Noch schneller und außerdem im Kopf geht es mit 2² = 4 ≡ –1 mod 5.

---

Hier mal die Rechnung nach meinem zweiten Vorschlag:

x = 2^578347903 = 2^{1+2*289173951} = 2*4^289173951 ≡ 2*(-1)^289173951 = -2 ≡ 3 mod 5

(Auch andere Rechenwege sind denkbar.)

---

Nun mal die Rechnung unter Ausnutzung von 2⁴ = 16 ≡ 1 mod 5,
was es erlaubt, den Exponenten mod 4 zu verkleinern:

x = 2^578347903 ≡ 2^{578347903 mod 4} ≡ 2³ = 8 ≡ 3 mod 5

---

Wieso darf ich dort einfach modulo 4 im exponenten benutzen benutzen?

---

Ich notiere es etwas anders, es ist

x = 2^578347903 = 2^{3+4*144586975} = 8*16^144586975 ≡ 3*1^144586975 = 3 mod 5

Da steckt unter anderem 2^4 = 16 ≡ 1 mod 5 drin. Dazu gibt es auch einen allgemeinen Satz, den ich hier aber gar nicht explizit benutzt habe.