restklassen berechnen

04.04.2011, 14:21

romana2007

restklassen berechnen

Meine Frage:
ich möchte diese berechnen
$\begin{eqnarray*} x^2\equiv 1 mod 7 \end{eqnarray*}$
und
$\begin{eqnarray*} x^6 \equiv 1 mod 7 \end{eqnarray*}$

Meine Ideen:
ich habe keine ideen

04.04.2011, 14:26

tmo

Auf diesen Beitrag antworten »

Erstere Gleichung hat in jedem Körper die selben Lösungen. Sollte also kein Problem sein.

Und für die zweite Aufgabe betrachte man den kleinen Satz von Fermat.

04.04.2011, 14:27

jester.

Auf diesen Beitrag antworten »

Hallo,

die Lösungen von $\begin{eqnarray*} x^2\equiv 1 \pmod 7 \end{eqnarray*}$ bzw. $\begin{eqnarray*} x^6\equiv 1 \pmod 7 \end{eqnarray*}$ zu finden, ist die gleiche Aufgabe, wie die Polynome $\begin{eqnarray*} X^2-1, ~ X^6-1 \end{eqnarray*}$ im Polynomring $\begin{eqnarray*} \mathbb{F}_7[X] \end{eqnarray*}$ zu faktorisieren. Beachte dabei, dass $\begin{eqnarray*} \mathbb F _7 \end{eqnarray*}$ ein Körper ist.
Suche zunächst also Nullstellen der Polynome, da gibt es ein paar offensichtliche Kandidaten. Für die restlichen Faktoren kann man die Elemente von $\begin{eqnarray*} \mathbb{F}_7 \end{eqnarray*}$ durchprobieren, es sind ja nur 7 Stück.

Edit: tmo hat Recht, Fermat geht hier natürlich auch gut. Irgendwie denke ich ganz oft nicht an diesen speziellen Satz Hammer

04.04.2011, 14:53

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von jester.
Für die restlichen Faktoren kann man die Elemente von $\begin{eqnarray*} \mathbb{F}_7 \end{eqnarray*}$ durchprobieren, es sind ja nur 7 Stück.

Gut, dass du das erwähnt hast. Frei nach dem Motto, dass man seine Methoden der Schwierigkeit der Aufgabe anpassen sollte, ist das eigentlich die sinnvollste Lösung.

Zumindest kann ich es nicht verstehen, warum diese Methode immer wieder missachtet wird, es ist doch wirklich das leichteste der Welt bei kleinen Modulos einfach alle Restklassen durchzuprobieren. Dazu ist es auch sehr effektiv und man löst mit $\begin{eqnarray*} f(x) \equiv c \pmod m \end{eqnarray*}$ auch gleich noch $\begin{eqnarray*} f(x) \equiv C \pmod m \end{eqnarray*}$ für alle $\begin{eqnarray*} C \in \mathbb Z/m\mathbb Z \end{eqnarray*}$ .

Wenn man sich das ein einziges mal bewusst macht, sind solche Aufgaben nie wieder ein Problem.

Neue Frage »

Antworten »

restklassen berechnen

Verwandte Themen