Fragen zu Gleichungen mit Modulo

09.07.2008, 15:46

ChaosNo1

Fragen zu Gleichungen mit Modulo

Hallöchen

Ich sitzt hier gerade beim Mathe Pauken und hab mal ein paar Fragen zu Lösen von Gleichungen mit Modulo, mir sind die Lösungswege nicht ganz klar, bzw möchte ich fragen, ob der eingeschlagene Lösungsweg so richtig ist Augenzwinkern

Aufgabentyp 1:

354n = 7 mod(133)

Mein Lösungsweg:

354n = 133y +7 ->
354n -133y = 7

jetzt löse ich die diophantische Gleichung mit dem erweiterten Euklid und schau mir als Lösung nur das n an, wobei die Lösung die allgemeine (mit dem Faktor k) ist.

Voraussetzung ist: ggt = (a,m) = 1

Hab ich das soweit richtig verstanden?

Aufgabentyp 2:

BSP:
345 = 17 mod n

Mein Lösungsweg:
345-17 = 0 mod n
328 = 0 mod n

Jetzt mach ich bei der 328 eine Primfaktorzerlegung:
328 = 2 x 2 x 2 x 41

Jetzt käme doch als Lösung für n alle möglichen "kombinationen" der primfaktoren in frage, also 2, 2x2, 2x2x2, 41, 2x41, 2x2x41, 2x2x2x41

Stimmt das? Und wie geben ich das am besten als Lösung an? Könnten ja auch mal mehr Faktoren sein Augenzwinkern

Wo ich grad gar keine Idee habe ist

Aufgabentyp 3 :

n = 234 mod(11)

und

39 = n mod 5

sieht ja recht einfach aus, aber ich bin mir unsicher, ob man da jetzt nicht auf irgendwie alle Lösungen für n angeben kann/muss/soll, also irgendwas mit nem faktor k Augenzwinkern

Vielen Dank Augenzwinkern

10.07.2008, 01:26

mYthos

Auf diesen Beitrag antworten »

Zu 1)

$\begin{eqnarray*} 354n = 133k + 7 \end{eqnarray*}$

$\begin{eqnarray*} n = \frac{133k + 7}{354} \ \ k \in \mathbb{Z} \end{eqnarray*}$

Zu 2)

Deine Überlegung ist richtig,

$\begin{eqnarray*} n = \frac{328}{k} \end{eqnarray*}$

wobei n ganzzahlig sein muss, somit kommen alle Teiler von 328 in Frage (n ist Element der Teilermenge von 328)

Zu 3)

Da 234(11) = 3, ist

$\begin{eqnarray*} n = 3 + 11k \ \text{mit} \ k \in \mathbb{Z} \end{eqnarray*}$

und bei

39 = n(5) ersetzen wir 39 zunächst durch 4 (n(5) ist kleiner als 5):

4 = n(5) -> n = ..., 4, 9, ...

$\begin{eqnarray*} n = 4 + 5k \ \ k \in \mathbb{Z} \end{eqnarray*}$

mY+

10.07.2008, 10:43

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von mYthos
Zu 1)

$\begin{eqnarray*} 354n = 133k + 7 \end{eqnarray*}$

$\begin{eqnarray*} n = \frac{133k + 7}{354} \ \ k \in \mathbb{Z} \end{eqnarray*}$

Und was soll das bringen?

Der erweiterte euklidische Algorithmus liefert die Darstellung $\begin{eqnarray*} 1 = 65\cdot 354-173\cdot 133 \end{eqnarray*}$ , also
$\begin{eqnarray*} 354^{-1}\equiv65\pmod{133} \end{eqnarray*}$ . Daraus folgt $\begin{eqnarray*} n\equiv 7\cdot 65=56\pmod{133} \end{eqnarray*}$ .

11.07.2008, 12:20

ChaosNo1

Auf diesen Beitrag antworten »

Danke erstmal soweit für die Antwort.

DIe 1. Aufgabe jetzt also doch mit euklid lösen?

Ich hab das mal probiert, habe dabei aber nur das x bzw, das n betrachtet und y ignoriert. Soweit ich das richtig verstanden habe, liefert mir euklid hier das multiplikative Inverse des Faktors e vor dem n, sofern ggt(e,m)=1, also mein Algorithmus bei 1 (oder auch -1 ????) ankommt. Würde er es nicht, wäre die Gleichung nicht lösbar

Leider komm ich irgendwie mit dem Editor hier nicht klar, bzw meckert er immer, wenn ich aus Mathtype Latex-Code einfüge. Deswegen mal als Bild

http://img187.imageshack.us/img187/5243/euklidst7.gif

Ist das die einzigste Lösung

oder gibt es mehr.

Ich denke da an 56 + k*133

Danke Augenzwinkern

11.07.2008, 12:40

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von ChaosNo1
Ist das die einzigste Lösung

oder gibt es mehr.

Ich denke da an 56 + k*133

Danke Augenzwinkern

Kommt drauf an, "wo" man sich befindet: In $\begin{eqnarray*} \mathbb Z/133\mathbb Z \end{eqnarray*}$ ist $\begin{eqnarray*} x=\overline{56} \end{eqnarray*}$ (die zur Zahl 56 gehörende Restklasse) die eindeutig bestimmte Lösung der Gleichung $\begin{eqnarray*} \overline{354}\cdot x=\overline{7} \end{eqnarray*}$ . In $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ sind alle Zahlen der Form $\begin{eqnarray*} 56+133k,k\in\mathbb Z \end{eqnarray*}$ Lösungen.

11.07.2008, 12:42

mYthos

Auf diesen Beitrag antworten »

Zitat:

Original von therisen
...
Und was soll das bringen?
...

Das bringt alle Lösungen für n, also auch die nicht ganzzahligen. Ich habe nicht gesehen, dass n unbedingt ganzzahlig sein soll.

mY+

11.07.2008, 12:57

ChaosNo1

Auf diesen Beitrag antworten »

ok, danke

17.07.2008, 22:57

ChaosNo1

Auf diesen Beitrag antworten »

Zitat:

Original von therisen

Zitat:

Original von ChaosNo1
Ist das die einzigste Lösung

oder gibt es mehr.

Ich denke da an 56 + k*133

Danke Augenzwinkern

Hallo nochmal.

Hab dazu nochmal eine dringende Frage.

Ich bekomme doch für das n 56 raus

nochmal kurz zu Erinnerung:

354n = 7 mod133

Das Inverse ist ja 65 (Inverses element von 88)

Wenn ich jetzt der Rechnung folge:

65 * 7 = 455 = 56 mod 133

ist dann die 56 wirklich mein n?

Wenn ich das mal einsetzte, bekomme ich:

354*56 =1 mod 133

also nicht 7

Wo ist da mein Fehler?

Danke!!!

17.07.2008, 23:02

Auf diesen Beitrag antworten »

Zitat:

Original von ChaosNo1
Wenn ich das mal einsetzte, bekomme ich:

354*56 =1 mod 133

also nicht 7

Wo ist da mein Fehler?

Rechne nochmal nach: Es kommt 7 raus, nicht 1.

17.07.2008, 23:06

ChaosNo1

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von ChaosNo1
Wenn ich das mal einsetzte, bekomme ich:

354*56 =1 mod 133

also nicht 7

Wo ist da mein Fehler?