x finden bei Kongruenz

18.02.2018, 13:27

Alice12

x finden bei Kongruenz

Meine Frage:
Hallo zusammen,
ich habe hier eine Aufgabe:
Ich soll das x finden für $\begin{eqnarray*} 128x \equiv 800 mod 2016 \end{eqnarray*}$ .
Da hab ich als erstes ggT(128,2016)=32. Dann habe ich die Kongruenz durch 32 geteilt, weil 128 durch 32 teilbar ist. Also gibt es ja eine Lösung.
Hab dann die Gleichung 4x=25 mod 63. Als nächstes hab ich wieder den euklidischen Algorithmus berechnen. Das Ergebnis war nun ggT(4,63)=1, 1 teilt ja auch 4. Wenn ich die kongruenz mit 1 teile bleibt die Gleichung ja so wie sie ist.

Meine Ideen:
Wie könnte ich das denn sonst noch lösen?

18.02.2018, 13:48

HAL 9000

Auf diesen Beitrag antworten »

RE: x finden bei Kongruenz

Zitat:

Original von Alice12
Ich soll das x finden für $\begin{eqnarray*} 128x \equiv 800 mod 2016 \end{eqnarray*}$ .
Da hab ich als erstes ggT(128,2016)=32. Dann habe ich die Kongruenz durch 32 geteilt, weil 128 durch 32 teilbar ist. Also gibt es ja eine Lösung.

Es gibt eine Lösung, weil die rechte Seite 800 durch 32 teilbar ist!

Zitat:

Original von Alice12
Hab dann die Gleichung 4x=25 mod 63. Als nächstes hab ich wieder den euklidischen Algorithmus berechnen. Das Ergebnis war nun ggT(4,63)=1

Das hättest du dir getrost sparen können, das Ergebnis 1 war schon klar, als du oben die Ausgangsgleichung durch 32 geteilt hast.

Schon eher Sinn hätte der Erweiterte (!) Euklidische Algorithmus gemacht, denn der liefert ganze Zahlen $\begin{eqnarray*} a,b \end{eqnarray*}$ mit $\begin{eqnarray*} 4a+63b=1 \end{eqnarray*}$ . Allerdings ist es auch so nicht schwer, passende Lösungen da sofort zu "sehen", etwa $\begin{eqnarray*} a=16,b=-1 \end{eqnarray*}$ . Und mit dem daraus folgenden $\begin{eqnarray*} 4^{-1}\equiv 16\bmod 63 \end{eqnarray*}$ kann dann auch die Kongruenz $\begin{eqnarray*} 4x\equiv 25\bmod 63 \end{eqnarray*}$ leicht gelöst werden.

18.02.2018, 15:14

Alice12

Auf diesen Beitrag antworten »

Danke Hal 9000,
für die schnelle Antwort.
Also laut Lösung soll x=1030 sein ohne die Lösung wäre ich jetzt einfach durch ausprobieren nicht drauf gekommen. Das würde bei mir eine Ewigkeit dauern. Den erweiterten euklidischen Algorithmus hab ich berechnet und komme auf
1=-1* 63+4*16 weiter weiß ich nicht so richtig mich stört halt das da -1*63 steht. unglücklich

18.02.2018, 15:21

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Alice12
Also laut Lösung soll x=1030 sein

Wer sagt das? Es gibt eine eindeutige Lösung modulo 63, dem entsprechen aber dann 32 Lösungen modulo 2016. Eine dieser 32 Lösungen ist tatsächlich 1030, es gibt aber keinen Grund, warum die anderen 31 Werte keine Lösungen sein sollen - es sei denn, es gibt auch noch anderere Forderungen an $\begin{eqnarray*} x \end{eqnarray*}$ , welche du oben verschwiegen hast...

Zitat:

Original von Alice12
komme auf 1=-1* 63+4*16 weiter weiß ich nicht so richtig mich stört halt das da -1*63 steht.

1) Was stört dich daran?
2) Hast du meinen Beitrag auch wirklich bis zum Schluss durchgelesen?

18.02.2018, 15:49

Alice12

Auf diesen Beitrag antworten »

Naja weil die Restklasse dann negativ ist bei -1*63 das stört mich.
Ich hab was versucht. Wie du schon gemerkt hast, ich bin noch unsicher bei solchen Aufgaben, weil ich nicht genau weiß was ich darf und was nicht aber ich versuchs mal
1=-1*63+4*16
1*63=-1+4*16
1*63-4*16=-1:-16
$\begin{eqnarray*} 16^{-1}=4 mod 63 \end{eqnarray*}$ verwirrt

Die Aufgabe gehört zu einer viel anderen Aufgabe, nämlich zum Pollard-rho-Algorithmus mit dem ich den diskreten Logarithmus berechnen soll. Hab alles verstanden bis auf diesen Teil. Hab von gestern bis heute morgen 2 Uhr dran gesessen und weil ich das jetzt immer noch nicht verstanden habe, habe ich es jetzt hier hochgelanden.

Die Lösung zu dem Teil hänge ich mal an.

18.02.2018, 15:57

HAL 9000

Auf diesen Beitrag antworten »

Ok, also war das

Zitat:

Original von HAL 9000
es sei denn, es gibt auch noch anderere Forderungen an $\begin{eqnarray*} x \end{eqnarray*}$ , welche du oben verschwiegen hast...

zutreffend.

18.02.2018, 16:05

Alice12

Auf diesen Beitrag antworten »

Kann ich das jetzt nicht mehr normal ausrechnen und ist mein Ansatz überhaupt richtig?

18.02.2018, 18:25

HAL 9000

Auf diesen Beitrag antworten »

Wir waren (schon länger) bei $\begin{eqnarray*} 4^{-1}\equiv 16\bmod 63 \end{eqnarray*}$ angelangt, daher ist die Lösung deiner Kongruenz $\begin{eqnarray*} 4x\equiv 25\bmod 63 \end{eqnarray*}$ gleich

$\begin{eqnarray*} x\equiv 4^{-1}\cdot 25\equiv 16\cdot 25 = 400\equiv 22\bmod 63 \end{eqnarray*}$ ,

und dieses $\begin{eqnarray*} x\equiv 22\bmod 63 \end{eqnarray*}$ ist die Lösung der Kongruenz $\begin{eqnarray*} 4x\equiv 25\bmod 63 \end{eqnarray*}$ , und folglich auch die Lösung der Ausgangskongruenz $\begin{eqnarray*} 128x\equiv 800\bmod 2016 \end{eqnarray*}$ .

Neue Frage »

Antworten »

x finden bei Kongruenz

Verwandte Themen