Restklassen und Kongruenz

12.03.2007, 22:27

Julz

Restklassen und Kongruenz

Hi,
Ich hab folgende Aufgabe:

7 $\begin{eqnarray*} \equiv \end{eqnarray*}$ r mod 9
11 $\begin{eqnarray*} \equiv \end{eqnarray*}$ r mod 14
17 $\begin{eqnarray*} \equiv \end{eqnarray*}$ r mod 25

Meine Lösungsansätze sind ungefähr dieselben die ich aus einem skript kopiert habe, allerdings ist ganz am ende ein Schritt mehr als ich gemacht habe und mir ist absolut nicht klar wie man daruf kommen soll. Vielleicht kann mir ja jemand von euch weiter helfen.

1. Schritt: Wir bestimmen zunächst alle s $\begin{eqnarray*} \in \end{eqnarray*}$ Z, für die gilt

(1)

7 $\begin{eqnarray*} \equiv \end{eqnarray*}$ s mod 9,

11 $\begin{eqnarray*} \equiv \end{eqnarray*}$ s mod 14

Eine ganze Zahl s $\begin{eqnarray*} \in \end{eqnarray*}$ Z erfüllt genau dann die Relationen (1), wenn gilt

(2)

s $\begin{eqnarray*} \in \end{eqnarray*}$ (7 + 9Z) "Schnittmenge" (11 + 14Z),

d.h. wenn es x, y $\begin{eqnarray*} \in \end{eqnarray*}$ Z gibt, so dass gilt

(3)

s = 7 + 9x = 11 + 14y.

Durch Umformung erhalten wir aus (3) die diophantische Gleichung

(4)

9x - 14y = 11 - 7 = 4.

Umgekehrt liefert jede Lösung (x, y) $\begin{eqnarray*} \in \end{eqnarray*}$ Z × Z der Gleichung (4) durch

s := 7 + 9x =11 + 14y eine Lösung von (1) bzw. (2).

Zur Lösung der Gleichung (4) benutzen wir den erweiterten Euklidischen Algorithmus:

14 = 1 · 9 + 5,

9 = 1 · 5 + 4,

5 = 1 · 4 + 1.

Daraus folgt

1 = 5 - 1 · 4 = 5 - (9 - 5) = -9 + 2 · 5 = -9 + 2(14 - 9) = 9 · (-3) - 14 · (-2),

also

{(x, y) $\begin{eqnarray*} \in \end{eqnarray*}$ Z × Z : 9x - 14y = 4} = {(-12 - 14q, -8 - 9q) $\begin{eqnarray*} \in \end{eqnarray*}$ Z × Z : q $\begin{eqnarray*} \in \end{eqnarray*}$ Z}.

Daher erfüllt s $\begin{eqnarray*} \in \end{eqnarray*}$ Z genau dann die Relationen (1), wenn es ein q $\begin{eqnarray*} \in \end{eqnarray*}$ Z gibt, so dass gilt

s = 7 + 9(-12 - 14q) = 11 + 14(-8 - 9q) = -101 + 126 · (-q).

Dies ist gleichbedeutend mit

s $\begin{eqnarray*} \in \end{eqnarray*}$ -101 + 126Z = 25 + 126Z, -----Wie kommt man auf diesen Schluss??

bzw. 25 $\begin{eqnarray*} \equiv \end{eqnarray*}$ s mod 126

Von 25 + 126Z nach 25 $\begin{eqnarray*} \equiv \end{eqnarray*}$ s mod 126 zu kommen ist ja wieder klar aber wie kommt man auf diesen zwischenschritt in der beispiel rechnung steht nichts weiter drin und ich versteh auch den sinn nicht warum man diesen schritt machen soll. verwirrt

Bin für jede Idee dankbar.

MFG Julz

13.03.2007, 17:51

Abakus

Auf diesen Beitrag antworten »

RE: Restklassen und Kongruenz

Zitat:

Original von Julz
Dies ist gleichbedeutend mit

s $\begin{eqnarray*} \in \end{eqnarray*}$ -101 + 126Z = 25 + 126Z, -----Wie kommt man auf diesen Schluss??

bzw. 25 $\begin{eqnarray*} \equiv \end{eqnarray*}$ s mod 126

Du "addierst" einmal 126. Schließlich rechnest du hier modulo 126, so dass du zB Vielfache von 126 addieren darfst.

Natürlich ist das nicht sauber hingeschrieben, weil da eigentlich Mengen stehen sollten. Wenn du dir diese hinschreibst, wird es richtig.

Grüße Abakus smile

Neue Frage »

Antworten »

Restklassen und Kongruenz

Verwandte Themen