x^9 = 8 mod 15 (Wie löst man das am besten? phi funktion? wenn ja, wie? )

Question

Hallo ich bräuchte mal kurz Hilfestellung. Kommt man da mit der phi Funktion weiter? Wenn ja, dann wie? wie wende ich sie darauf an?

Vielen Dank

Answer 1

Kommt man da mit der phi Funktion weiter? Wenn ja, dann wie? wie wende ich sie darauf an?

Ja, das wäre eine Möglichkeit: $$ x^9 \equiv x^{9 \text{ mod }\varphi(15) } \equiv x \equiv 8 \text{ mod } 15. $$(vgl. Satz von Euler-Fermat)

Comments

Das ist ja eine Superlösung, aber wie ist es mit der Vor.   ggt(x,15)=1 , kann man das so annehmen

oder muss man da noch extra was prüfen ?

---

Das ist ein berechtigter Einwand, ich habe darüber nicht weiter nachgedacht.

---

Im vorliegenden Fall ist es so, dass die 15er-Reste der 9er-Potenzen alle verschieden sind. Daher besitzt die vorliegende Kongruenzgleichung genau eine Lösung. Im allgemeinen ist das aber nicht so, weswegen meine Antwort nur mit Vorsicht zu genießen ist, wenn man auf diese Weise alle Lösungen bestimmen will.

---

Im vorliegenden Fall ist es so, dass die 15er-Reste der 9er-Potenzen alle verschieden sind.

Genau, das hatte ich auch herausgefunden. Allerdings wäre das ja im Rahmen etwa einer 

Klausuraufgabe (ohne Rechner) schon etwas aufwändiger zu prüfen. Oder vielleicht doch nicht

0³ ≡ 0 mod 15
1³ ≡ 1 mod 15
2³ ≡ 8 mod 15
3³ = 27 ≡ 12 mod 15
4³ =4*16 ≡ 4*1 mod 15
5³ =25*5≡ 10*5 ≡ 5mod 15
6³ =36*6≡ 6*6 ≡ 6 mod 15
7³ =49*7≡ 4*7 ≡-2 ≡ 13 mod 15

und wegen 8≡-7 mod 15 und 9≡-6 mod 15 etc.
kann man die anderen über (-x)³ = - x³ erledigen.

Also x=8 einzige Lösung in ℤ/8ℤ.

---

Noch weniger aufwändig ist es, die beiden Kongruenzen modulo 3 und modulo 5 einzeln zu prüfen.

---

Ok, jetzt mal mit der Zerlegung der Kongruenz:

$$x^9 \equiv 8 \text{ mod }15 \\ x^9 \equiv 8 \text{ mod }3 \quad\land\quad x^9 \equiv 8 \text{ mod }5 \\x^{9 \text{ mod }\varphi(3)} \equiv 8 \text{ mod }3 \quad\land\quad x^{9 \text{ mod }\varphi(5)} \equiv 8 \text{ mod }5 \\x^1 \equiv 8 \text{ mod }3 \quad\land\quad x^1 \equiv 8 \text{ mod }5 \\x \equiv 8 \text{ mod }15.$$Sieht tatsächlich recht einfach aus. Ist das so logisch und darstellerisch so richtig oder habe ich etwas übersehen?

---

Immer noch mit dem Einwand: Gilt ggt(x,3)=ggt(x,5)=1

---

Die Teilerfremdheit zu den beiden Primzahlen 3 und 5 gilt für alle x mit Ausnahme der 0, die hier als Lösung ohnehin nicht in Frage kommt.

Answer 2

x⁹ = (x³)³ und 8 = 2³ also hat man eine Lösung,

wenn x³ ≡ 2 mod 15

und das klappt für x=8.

Comments

Vollständig kann man angeben

x = 8 + 15n ; n ∈ Z

---

ehm joa, das ist mir jetzt nicht ganz schlüssig. was hast du denn da genau gemacht? weil muss das ja allgemein auch verstehen.
und so hat man die anderen x von 0 bis 14 auser die 8 nicht in betracht gezogen

---

weil bei den anderen     x³ nicht kongruent zu 2 mod 15 gilt