Lösen Sie die Kongruenzgleichung

Question

Aufgabe:

Lösen Sie die Kongruenzgleichung

x³ +4x+1 ≡ 0 (mod24)

Sollten Sie hierbei auf Schwierigkeiten stoßen, so lösen Sie statt dessen das System simultaner Kongruenzen

  x ≡ 1(mod3)

  x ≡ 4 (mod5)

 x ≡ -3 (mod7)

Comments

Hallo,

x^3 +4x+1 ≡ 0 (mod24)

Du könntest die ganzen Zahlen von 0 bis 23 einsetzen und gucken, ob ein Vielfaches von 24 herauskommt. Der Aufwand kann aber verringert werden, da gerade Zahlen für x entfallen.

Sinnvoll finde ich, den Term so umzuformen, dass leichter gerechnet werden kann.

(x^2+4)*x+1=n*24

(x^2+4)*x=n*24-1

Für den Term auf der rechten Seite kommen in Frage 23; 47; 71; 95; 119; 143; ...

Die ersten drei kommen nicht infrage, da es Primzahlen sind. Bei 95 könnte x=5 oder x=-5 versucht werden.

(5^2+4)*(-5)+1=-29*5+1≡-5*5+1=-24≡0 mod 24

-5 bzw. 24-5=19 ist also eine Lösung.

Ob es noch mehr gibt?

:-)

Answer 1

Zur Teilung durch 24 ist die Teilbarkeit durch 8 und durch 3 erforderlich. x kann nicht gerade sein, sonst wäre x³+4x+1 ungerade. Also ist x ungerade, und 4x lässt den Rest 4 bei Teilung durch 8, 4x+1 dann den Rest 5 mod 8.

Für x³ muss somit x³ kongruent 3 mod 8 gelten.

Da x² für ungerade Zahlen prinzipiell kongruent 1 mod 8 ist, ist x³ kongruent 3 mod 8 nur mit  x kongruent 3 mod 8 zu erreichen. In Frage kommen also 3, 11 und 19.

Durch 3 ist x³ +4x+1 nur im Fall x=19 teilbar.

Answer 2

Ähnliches Verfahren wie bei abakus:

\(x^3+x+1\equiv 0\) mod \(3\) liefert \(x\equiv 1\) mod \(3\).

Ferner ist \(x\) wegen \(x^3+1\equiv 0\) mod \(2\) ungerade.

Damit kommen mod \(24\) als positive Reste nur \(\{1,7,13,19\}\)

bzw. als betragskleinste die Reste \(\{1,7,-11,-5\}\) in Frage.