Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Lineare Kongruenz lösen

Lineare Kongruenz lösen

Universität / Fachhochschule

Elementare Zahlentheorie

Tags: Elementare Zahlentheorie, Erweiterter Euklidischer Algorithmus, Euklidischer Algorithmus

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Tuxax

Tuxax aktiv_icon

00:08 Uhr, 08.11.2010

Antworten
Hallo!

Ich bin gerade am verzweifeln, da ich das folgende Beispiel einfach nicht fertig lösen kann.

"Lösen Sie die folgenden Kongruenzen (d.h. Gleichungen in Restklassen in Z) bzw. beweisen Sie die Unlösbarkeit ( in Z)"

a)8x≡4(mod16)
b)8x≡4(mod15)

Zu a)
Lineare Kongruenz hat eine Lösung, wenn ggT(8,16) |4
Der ggT(8,16) =8→8 teil nicht 4
Damit ist bewiesen, dass a keine Lösung hat mMn.

Zu b)
ggT(8,15) =1→1 teilt 4→ Es existiert exakt eine Lösung für x

Jetzt scheitert es jedoch daran diese Lösung zu finden... ich habe es (wie ich im Internet gesucht habe) mit dem erweiterten Euklidischen Algorithmus probiert - sprich es ist die Rede davon, das multiplikativ Inverse von a, also 8 zu finden.

Ich fange vorher mit dem Euklidischen Algorithmus von vorne an, um den ggT(8,15) zu finden, den ich zuvor ohne den Algorithmus bestimmt habe:

15=8⋅1+7
8=7⋅1+1→1 Rest
7=1⋅7+0

Nun der erweiterte Euklidische Algorithmus um das multiplikativ Inverse zu finden:
1=8-7⋅1
1=8-(15-8⋅1)⋅1
1=8-15⋅1+8⋅1
1=8⋅2-15⋅1

Jetzt weiß ich aber nicht mehr weiter :(
So ähnlich hat es ein Student in einem eigenen Wiki für unsere Uni gemacht, jedoch multipliziert er ab hier 4 in die Gleichung hinein:

4=8⋅2⋅4-15⋅1⋅4

Jetzt behauptet er, dass x=2⋅4 ist (was für komischerweise auch stimmt, aber nicht so richtig Sinn ergibt, da ich das nicht ganz nachvollziehen kann warum man mit 4 multiplizieren muss)

Ich hoffe ihr könnt mir weiterhelfen und das Beispiel vollständig lösen - ich bin mit meinem Latein am Ende

Vielen Dank im Voraus!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."
Online-Nachhilfe in Mathematik
Antwort
BjBot

BjBot aktiv_icon

00:24 Uhr, 08.11.2010

Antworten
8x≡4(mod15)

Ziel ist es ja, dass das x links allein steht.
Jetzt könnte man natürlich das Inverse von 8 modulo 15 von Hand mit dem "EEA" berechnen.
Mit geübtem Blick könnte man aber auch schon direkt sehen, dass wenn man links 2 dazu multipliziert, dann 2⋅8=16 entsteht, was natürlich direkt kongruent zu 1 modulo 15 ist.
Und damit ist man dann im Endeffekt schon am Ziel, denn es folgt x≡2⋅4=8(mod15)
Tuxax

Tuxax aktiv_icon

00:42 Uhr, 08.11.2010

Antworten
Nachdem ich mir deine Antwort jetzt ein paar mal durchgelesen habe ein paar Frage:

- Heißt lineare Kongruenzen lösen, dass man für x am Ende konkrete Werte hat (x=..), oder das man diese Form, wie du sie gezeigt hast hat (x≡.. mod(..))- ist ne blöde Frage, aber ich kenn mich da noch zu wenig aus :(

- "Mit geübtem Blick könnte man aber auch schon direkt sehen, dass wenn man links 2 dazu multipliziert, dann 2⋅8=16 entsteht, was natürlich direkt kongruent zu 1 modulo 15 ist." - Was bringt es wenn ich weiß, dass 16≡1(mod15) ist?

- Könntest du deine Folgerung ein bisschen näher erklären "denn es folgt x≡2⋅4=8(mod15)"? (Ich weiß ich bin lästig, aber ich bitte dich drum dir die Zeit zu nehmen :-) )

lg
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.