Modulo, vierter Potenzrest

Question

Hallo kann mir jemand bei dieser Aufgabenstellung bitte helfen?

Ich soll x⁴ ≡ 38 mod 209 berechnen. Jetzt weiß ich, dass 209 = 11*19 das kann ich dann ja zerlegen in

x⁴ ≡ 38 mod 11

x⁴ ≡ 38 mod 19

richtig?

Nun komme ich nicht mehr weiter..

Answer 1

x⁴ ≡ 38 mod 11

x⁴ ≡ 38 mod 19

also sogar

x⁴ ≡ 5 mod 11

x⁴ ≡ 0 mod 19


also ist x⁴ durch 19 teilbar und


weil 19 prim ist, ist auch x durch 19 teilbar.


Und wenn du es mit x=19 bzw  x=2*19  bzw. x=3*19

versuchst, hats du schon Erfolg:

57⁴ = 10555996 ≡ 5 mod 11

also auch  10555996 ≡ 38 mod 209

Comments

Vielen lieben Dank, das habe ich nun verstanden aber jetzt hänge ich an der nächsten Aufgabe:

Umgeformt ergibt sich

x^3 kongruent 7 modulo 11

x^3 kongruent 7 modulo 19

Wie gehe ich da vor?

Und wie stelle ich fest, dass

x^5 kongruent 37 mod 209 keine Lösung hat?

---

x³ kongruent 7 modulo 11

x³ kongruent 7 modulo 19

Wie gehe ich da vor?

Modulo 11 gibt es ja nicht so sehr viele

Reste, nämlich nur 0 bis 10.

Wenn du die hoch 3 nimmst, merkst du bei

der ersten Kongruenz

es passt nur  6³ = 216 kongruent 7 modulo 11

und mod 19 ist das auch 7 .


x⁵ kongruent 37 mod 209 keine Lösung hat?

hattest du ja oben schon, das gibt

x⁵ ≡ 37 mod 11

x⁵ ≡ 37 mod 19

also sogar 

x⁵ ≡ 4 mod 11 

x⁵ ≡ 18 mod 19   bzw   =   -1 mod 19

also auch x kongruent -1  mod  19 .

Aber x=18 erfüllt nicht  x⁵ ≡ 4 mod 11

Answer 2

x⁴ ≡ 38 mod 19.  Der Rest (38) kann nur dann das doppelte des Teilers (19) sein, wenn x⁴ selbst durch 19 teilbar ist. Dann muss x ein Vielfaches von 19 sein. Hilft das weiter?