0 Daumen
1,1k Aufrufe

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.


Avatar von

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

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

1 Antwort

0 Daumen

<?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}\)

Avatar von 107 k 🚀

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

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community