Rechnen in Restklassen vol.2

17.02.2014, 14:57

Babygrande

Rechnen in Restklassen vol.2

Hallo zusammen!
Meine Frage ist im Zusammenhang mit Restklassen, wie ich im Titel geschrieben habe. Zuerst möchte ich sagen, dass ich ein anderes Thema hier gesehen habe und das ist genau, was in einer der alten Klausuren steht, aber ich habe noch andere, die ich versucht habe, zu rechnen, aber bin nich sicher, ob es richtig gemacht ist.

Also meine andere Beispiele sind:
1. Geben Sie in $\begin{eqnarray*} \mathbb Z_{192} \end{eqnarray*}$ eine Lösung von x.156 = 108 an.
2. Geben Sie in $\begin{eqnarray*} \mathbb Z_{825} \end{eqnarray*}$ eine Lösung von x.682 = 616 an.

Zu 1:
ggT(192,156) = $\begin{eqnarray*} \lambda \end{eqnarray*}$ .192 + $\begin{eqnarray*} \mu \end{eqnarray*}$ .156 = 12
$\begin{eqnarray*} \lambda \end{eqnarray*}$ = -4
$\begin{eqnarray*} \mu \end{eqnarray*}$ = 5

Dann forme ich ein bisschen um:
a = 156x
b = 108
n = 192
In dieser Formel einsetzen: a - b = q.n
156x - 108 = 192.q
Umformen zu x.156 + q.192 = 108 (hier verstehe ich nicht, warum das so ist, da wenn wir q.192 auf der anderen Seite schmeißen, dann soll es 156.x - q.192 = 108 sein, glaube ich :/ )
Von dem Euklidischen Algorthimus ist 5.156 - 4.192 = 12
108 ist aber 9.12
9.(5.156 - 4.192) = 12.9
45.156 - 36.192 = 108, d.h. x = 45, q= -36

Laut der Erklärung im anderen Thema soll ich dann x=45 aus 192 subtrahieren, um eine Lösung zu finden. Ich verstehe aber nicht, warum ich das machen soll und wie kann ich mein Ergebniss überprüfen?

Das andere Beispiel habe ich genauso wie das gemacht.
Also zu 2:
ggT(825,682) = $\begin{eqnarray*} \lambda \end{eqnarray*}$ .825 + $\begin{eqnarray*} \mu \end{eqnarray*}$ .682 = 11
$\begin{eqnarray*} \lambda \end{eqnarray*}$ = -19
$\begin{eqnarray*} \mu \end{eqnarray*}$ = 23
Am Ende aber kommt etwas Seltsames raus .. x habe ich gleich 1288 gefunden und es ist größer als 825.

Ich würde mich auf Antworten freuen.
Vielen Dank im Voraus!

P.S. Ich entschuldige mich, wenn ich Fehler gemacht habe, Deutsch ist nicht meine Muttersprache.

17.02.2014, 15:38

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Laut der Erklärung im anderen Thema soll ich dann x=45 aus 192 subtrahieren, um eine Lösung zu finden. Ich verstehe aber nicht, warum ich das machen soll und wie kann ich mein Ergebniss überprüfen?

x=45 ist eine Lösung, wie man leicht durch Einsetzen in die Gleichung sehen kann.

Zitat:

x habe ich gleich 1288 gefunden und es ist größer als 825.

1288 ist ein Lösung. Wenn es stört, dass das kein Standardrepräsentant ist reduziert man halt auf einen: $\begin{eqnarray*} 1288 \equiv 463 \mod 825 \end{eqnarray*}$

Wobei man das ganze hier aber auch durchaus geschickter angehen kann um die Größe der beteiligten Zahlen zu reduzieren. Es gilt $\begin{eqnarray*} a\equiv b \mod n \Leftrightarrow \frac{a}{d} \equiv \frac{b}{d} \mod \frac{n}{d} \end{eqnarray*}$ mit $\begin{eqnarray*} d=ggT(a,b,n) \end{eqnarray*}$ .

Damit wird z.B. aus der ersten Gleichung:
$\begin{eqnarray*} x\frac{156}{12} \equiv \frac{108}{12} \mod \frac{192}{12} \Leftrightarrow x\cdot 13 \equiv 9 \mod 16 \end{eqnarray*}$

17.02.2014, 20:00

Babygrande

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Original von Captain Kirk
Hallo,

Zitat:

x=45 ist eine Lösung, wie man leicht durch Einsetzen in die Gleichung sehen kann.

Oh, ja .. Ich habe daran nicht gedacht, danke.

Zitat:

Wobei man das ganze hier aber auch durchaus geschickter angehen kann um die Größe der beteiligten Zahlen zu reduzieren. Es gilt $\begin{eqnarray*} a\equiv b \mod n \Leftrightarrow \frac{a}{d} \equiv \frac{b}{d} \mod \frac{n}{d} \end{eqnarray*}$ mit $\begin{eqnarray*} d=ggT(a,b,n) \end{eqnarray*}$ .

Damit wird z.B. aus der ersten Gleichung:
$\begin{eqnarray*} x\frac{156}{12} \equiv \frac{108}{12} \mod \frac{192}{12} \Leftrightarrow x\cdot 13 \equiv 9 \mod 16 \end{eqnarray*}$

Achso! Das sieht ein bisschen leichter als das andere Verfahren aus. Ich werde es ausprobieren und üben smile

Vielen Dank für Deine Hilfe!
Noch eine Frage - wie bestimme ich das inverse Element einer Einheit in $\begin{eqnarray*} \mathbb Z_{30} \end{eqnarray*}$ ?

17.02.2014, 20:19

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

Achso! Das sieht ein bisschen leichter als das andere Verfahren aus. Ich werde es ausprobieren und üben

Das ist kein anderes Verfahren. Das ist nur eine Vorüberlegung um die Rechnung einfacher zu machen., bzw. um alle Lösungen zu erhalten.
Das x muss nach wie vor bestimmt werden, sei es durch scharfes Hinsehen oder wie zuvor mit dem erweiterten euklidischen Algorithmus.

Zitat:

Noch eine Frage - wie bestimme ich das inverse Element einer Einheit in $\begin{eqnarray*} \mathbb Z_{30} \end{eqnarray*}$ ?

Auch über den erweiterten euklidischen Algorithmus. Das Inverse Element x zu a modulo n ist ja nichts anderes als die Lösung von $\begin{eqnarray*} ax\equiv 1 \mod n \end{eqnarray*}$

17.02.2014, 20:23

Babygrande

Auf diesen Beitrag antworten »

Achso, gut. Danke wieder für Deine Hilfe! smile

Neue Frage »

Antworten »

Rechnen in Restklassen vol.2

Verwandte Themen