Modulo & Erweiterter Euklidischer Algorithmus

10.11.2018, 17:26

Ersti218

Modulo & Erweiterter Euklidischer Algorithmus

Meine Frage:
Hallo alle zusammen.
Ich hänge hier an einer Aufgabe fest, diese Lautet:

Zeigen Sie: Die Gleichung

$\begin{eqnarray*} a = b * x \,mod\,c (a,b,c\in \mathbb{Z}\,,0\leq a\leq c) \end{eqnarray*}$

hat genau eine Lösung $\begin{eqnarray*} x\in \mathbb{Z} \end{eqnarray*}$

, wenn die Zahl a durch die Zahl ggT(b,c) teilbar ist.

Meine Ideen:
Als spezifisches Beispiel haben wir die Formel:

9= 41*x mod 17

Zu berechnen dass ggT(41,17)=1 ist war kein großes Problem und natürlich ist 9 durch 1 teilbar.

Ich komm einfach nicht darauf wie man jetzt über den ggT auf x kommen soll.

11.11.2018, 15:10

Ersti218

Auf diesen Beitrag antworten »

RE: Modulo & Erweiterter Euklidischer Algorithmus
Ich hab fürs Beispiel inzwischen raus dass x=11 ist indem ich die Formel auf

a=((b mod c)*(x mod c)) mod c

umgeformt habe und nach dem einsetzen der Werte

9=((41 mod 17)*(x mod 17))mod 17

9=(7* (x mod 17))mod 17

einfach alle x von 0 bis 16 eingesetzt habe.

Dass hilft mir aber nicht wirklich dabei den beabsichtigten Rechen-weg zu finden.

11.11.2018, 15:13

URL

Auf diesen Beitrag antworten »

RE: Modulo & Erweiterter Euklidischer Algorithmus
Angenommen $\begin{eqnarray*} a=bx \bmod c \end{eqnarray*}$ . Dann gibt es ein $\begin{eqnarray*} k\in \mathbb{Z} \end{eqnarray*}$ mit $\begin{eqnarray*} a=bx+kc \end{eqnarray*}$ . Jetzt überleg dir, warum a durch die Zahl ggT(b,c) teilbar ist.

11.11.2018, 16:44

HAL 9000

Auf diesen Beitrag antworten »

Das "genau eine" in der Aufgabenstellung ist Unsinn. In ganzen Zahlen hat die Gleichung bei Erfülltsein der genannten Bedingung unendlich viele Lösungen, und selbst modulo $\begin{eqnarray*} c \end{eqnarray*}$ ist die Lösungsanzahl immerhin noch $\begin{eqnarray*} \operatorname{ggT}(b,c) \end{eqnarray*}$ . unglücklich

11.11.2018, 17:03

Ersti218

Auf diesen Beitrag antworten »

RE: Modulo & Erweiterter Euklidischer Algorithmus
Ich bin mir jetzt unsicher ob das richtig ist, aber ich hab mir jetzt zusammengedacht.

Aus a ist durch ggT(b,c) teilbar folgt

$\begin{eqnarray*} a=z*ggT(b,c) |z\in \mathbb{Z} \end{eqnarray*}$

mit $\begin{eqnarray*} ggT(b,c)=b*q+c*p \end{eqnarray*}$

erhält man die Formel

$\begin{eqnarray*} b*x+x*k=b*q*z+c*p*z \end{eqnarray*}$

mir ist nicht klar ob man dass noch umformen muss, aber mann kann daraus schließen

$\begin{eqnarray*} x=z*q \end{eqnarray*}$

Für das praktische Beispiel mit $\begin{eqnarray*} 9=41*x\, mod\,17 \end{eqnarray*}$

klappt das schon mal, jetzt bin ich mir aber nicht ganz sicher ob das als Begründung für einen allgemeinen beweis ausreicht.

11.11.2018, 17:42

URL

Auf diesen Beitrag antworten »

RE: Modulo & Erweiterter Euklidischer Algorithmus
Wenn das

Zitat:

$\begin{eqnarray*} b*x+\textcolor{red}c*k=b*q*z+c*p*z \end{eqnarray*}$

heißen sollte, kann man das stehen lassen.

11.11.2018, 19:26

Ersti218

Auf diesen Beitrag antworten »

RE: Modulo & Erweiterter Euklidischer Algorithmus
Kleiner Tippfehler.

Auf jeden Fall danke für die Hilfe und einen schönen Abend.

Neue Frage »

Antworten »

Modulo & Erweiterter Euklidischer Algorithmus

Verwandte Themen