Gleichung im Restklassenring lösen

Question

Aufgabe:

Bestimmt werden soll die Lösung der Gleichung x³ = 1 in ℤ/nℤ, wobei n ∈{61, 62, 63, 64}.

Es wäre ziemlich aufwendig für jedes Element aus ℤ/nℤ die Rechnung durchzuführen.

Comments

Ein Versuch für n = 61: Die Gleichung x³ = 1 ist äquivalen zu 0 = x³ - 1 = (x - 1)·(x² + x + 1).
Da ℤ/61ℤ ein Körper ist, gilt also x - 1 = 0 oder x² + x + 1 = 0.
Erste Lösung ist offenbar x₁ = 1.
Zweitens ist (immer modulo 61) 0 = x² + x + 1 = x² - 60x + 1 = (x - 30)² - 45.
Das Problem ist nun, ein z ∈ ℤ/61ℤ zu finden, für das z² = 45 gilt.
Mit etwas Mühe sieht man vielleicht, dass 45 = 289 = 17² ist.
Damit ist x₂ - 30 = 17, sowie x₃ - 30 = -17, d.h. x₂ = 47, x₃ = 13.

---

Und wie mache ich das jetzt für die anderen n, die keine Primzahlen sind?

Answer 1

<?php

$ns = [61,62,63,64];

printf("\\begin{aligned}\n");
foreach ($ns as $n) {
for ($x = 0; $x < $n; ++$x) {
  if (($x*$x*$x) % $n == 1) {
    printf("%d^3 &\\equiv 1 \mod %d\\\\", $x, $n);
  }
}
}
printf("\\end{aligned}\n");

\(\begin{aligned} 1^3 &\equiv 1 \mod 61\\13^3 &\equiv 1 \mod 61\\47^3 &\equiv 1 \mod 61\\1^3 &\equiv 1 \mod 62\\5^3 &\equiv 1 \mod 62\\25^3 &\equiv 1 \mod 62\\1^3 &\equiv 1 \mod 63\\4^3 &\equiv 1 \mod 63\\16^3 &\equiv 1 \mod 63\\22^3 &\equiv 1 \mod 63\\25^3 &\equiv 1 \mod 63\\37^3 &\equiv 1 \mod 63\\43^3 &\equiv 1 \mod 63\\46^3 &\equiv 1 \mod 63\\58^3 &\equiv 1 \mod 63\\1^3 &\equiv 1 \mod 64\\\end{aligned}\)

Comments

Kannst du mir auch erklären, wie man das berechnen kann?

---

Nein, kann ich nicht. Ich habe die Berechnung einem Computer überlassen.