Diophantische Gleichung

16.06.2018, 12:36

georg2000

Diophantische Gleichung

Hallo , es seien a,b ganze Zahlen und m eine natürliche größer 0. weiters ist g=ggt(a,m) und
$\begin{eqnarray*} ax\equiv b \end{eqnarray*}$ mod m . (1)

a) (1) hat genau dann eine Lösung wenn g|b
b) falls (1) eine Lösung hat , so hat (1) genau g Lösungen .

zu a) Wenn (1) eine Lösung hat dann gibt es ein $\begin{eqnarray*} x_0 \in Z : ax_0\equiv b \end{eqnarray*}$ mod m
das ist äquivalent zu $\begin{eqnarray*} m|(ax_0-b) \end{eqnarray*}$ das ist auch äquivalent zu ; es gibt ein $\begin{eqnarray*} y_0\in Z : my_0=ax_0-b \end{eqnarray*}$ , das ist äquivalent zu $\begin{eqnarray*} b=ax_0+(-m)y_0 \end{eqnarray*}$

das ist die diophantische gleichung welche Lösbar ist genau dann wenn ggt(a,-m)=ggt(a,m)=g|b

b) wenn nun (1) eine Lösung hatt dann gilt nach a) g|b.
es ist auch bekannt das x dann die form $\begin{eqnarray*} x_0+t*m/g \end{eqnarray*}$ mit einer ganzen Zahl t und einer speziellen Lösung x_0.

aber warum sollen es genau g verschiedene nun sein?
bzw stimmt mein a)?
Danke !!

16.06.2018, 12:40

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht entscheidest du dich zunächst mal, ob du $\begin{eqnarray*} \operatorname{ggt}(a,m) \end{eqnarray*}$ mit $\begin{eqnarray*} g \end{eqnarray*}$ oder $\begin{eqnarray*} d \end{eqnarray*}$ bezeichnen willst. Augenzwinkern

16.06.2018, 12:46

georg2000

Auf diesen Beitrag antworten »

sry , ich habe editiert und als g bezeichnet Freude

16.06.2018, 13:18

HAL 9000

Auf diesen Beitrag antworten »

Die Frage ist, was man schon als bekannt voraussetzen darf: Wenn du beispielsweise schon den Fall $\begin{eqnarray*} g=1 \end{eqnarray*}$ beherrschst, d.h.

Zitat:

Sind a,m teilerfremd, dann besitzt $\begin{eqnarray*} ax\equiv b \bmod m \end{eqnarray*}$ genau eine Lösung $\begin{eqnarray*} x\bmod m \end{eqnarray*}$

voraussetzen kannst, dann ist der Beweis ein leichtes.

16.06.2018, 15:21

georg2000

Auf diesen Beitrag antworten »

Hallo, nein den Sonderfall haben wir noch nicht gezeigt .
wenn a , m teilerfremd sind wie folgt dann die eindeutige Lösung?

16.06.2018, 15:36

HAL 9000

Auf diesen Beitrag antworten »

Wie weit müssen wir denn dann noch zurück, bis zum Urschleim...

Ist wenigstens das "Lemma von Bezout" bekannt?

16.06.2018, 15:36

georg2000

Auf diesen Beitrag antworten »

RE: dioph. glg
achso , wenn wir haben $\begin{eqnarray*} x=x_0+t*m/g=x_0+tm \end{eqnarray*}$ und dies eine Lösung ist
dann ist $\begin{eqnarray*} ax=a(x0+tm) \equiv b \end{eqnarray*}$ mod m .
dh aber dass $\begin{eqnarray*} m|[(ax_0-b)+atm] \end{eqnarray*}$ dh doch dass $\begin{eqnarray*} ax_0-b \equiv -atm \equiv 0 \end{eqnarray*}$
egal wie t gewählt wird .
dh nur eine Lösung .

16.06.2018, 15:38

georg2000

Auf diesen Beitrag antworten »

Das Lemma kennen wir , also dass g=xa+ym mit ganzen Zahlen x,y .

16.06.2018, 15:47

HAL 9000

Auf diesen Beitrag antworten »

Na das ist doch endlich mal ein Ansatzpunkt, wir müssen es nur wegen Namenskollision mit der Variablen $\begin{eqnarray*} x \end{eqnarray*}$ hier umformulieren:

Zitat:

Lemma von Bezout: Ist $\begin{eqnarray*} \operatorname{ggT}(a,m)=g \end{eqnarray*}$ , so gibt es ganze Zahlen $\begin{eqnarray*} u,v \end{eqnarray*}$ mit $\begin{eqnarray*} ua+vm=g \end{eqnarray*}$

Im Fall $\begin{eqnarray*} g=1 \end{eqnarray*}$ heißt das dann insbesondere $\begin{eqnarray*} ua\equiv 1\bmod m \end{eqnarray*}$ , d.h. $\begin{eqnarray*} u \end{eqnarray*}$ ist multiplikative Inverse zu $\begin{eqnarray*} a\bmod m \end{eqnarray*}$ . Damit kann man deine Gleichung schlicht multiplizieren und erhält $\begin{eqnarray*} uax\equiv ub\bmod m \end{eqnarray*}$ , also die eindeutige Lösung $\begin{eqnarray*} x\equiv ub\bmod m \end{eqnarray*}$ . Damit wäre dieser Fall $\begin{eqnarray*} g=1 \end{eqnarray*}$ abgehandelt.

Nun zum Fall $\begin{eqnarray*} g>1 \end{eqnarray*}$ :

1) Existiert ein $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ , dann bedeutet das $\begin{eqnarray*} m\mid (ax-b) \end{eqnarray*}$ und damit speziell auch $\begin{eqnarray*} t\mid (ax-b) \end{eqnarray*}$ für jeden Teiler $\begin{eqnarray*} t \end{eqnarray*}$ von $\begin{eqnarray*} m \end{eqnarray*}$ . Speziell gilt das auch für $\begin{eqnarray*} t=g \end{eqnarray*}$ , also $\begin{eqnarray*} g\mid (ax-b) \end{eqnarray*}$ , was zu $\begin{eqnarray*} g\mid b \end{eqnarray*}$ führt. Im Umkehrschluss heißt das, dass es im Fall $\begin{eqnarray*} g\not\mid b \end{eqnarray*}$ ein solches $\begin{eqnarray*} x \end{eqnarray*}$ nicht geben kann.

Sei andererseits $\begin{eqnarray*} g\mid b \end{eqnarray*}$ , dann setzen wir $\begin{eqnarray*} b=gb' \end{eqnarray*}$ sowie auch $\begin{eqnarray*} a=ga' \end{eqnarray*}$ und $\begin{eqnarray*} m=gm' \end{eqnarray*}$ mit ganzen Zahlen $\begin{eqnarray*} a',b',m' \end{eqnarray*}$ , und bekommen...

16.06.2018, 16:39

georg2000

Auf diesen Beitrag antworten »

okay der Fall g=1 ist mir klar.
falls g>1 .

wenn $\begin{eqnarray*} g|b \end{eqnarray*}$ dann erhalten wir aus $\begin{eqnarray*} ax \equiv b \end{eqnarray*}$ mod m
doch $\begin{eqnarray*} a'x \equiv b' \end{eqnarray*}$ mod m' .
da aber a' und m' teilerfremd sind , so führt uns das zu wieder zum fall g'=ggt(a',m')=1
was wir oben behandelt haben

16.06.2018, 17:03

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von georg2000
da aber a' und m' teilerfremd sind , so führt uns das zu wieder zum fall g'=ggt(a',m')=1
was wir oben behandelt haben

Exakt so ist es, es gibt also genau eine Lösung $\begin{eqnarray*} x\bmod m' \end{eqnarray*}$ , dem entsprechen die Werte $\begin{eqnarray*} x+km' \end{eqnarray*}$ mit ganzen Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ . Dies wiederum entspricht modulo $\begin{eqnarray*} m \end{eqnarray*}$ den insgesamt $\begin{eqnarray*} g \end{eqnarray*}$ verschiedenen Restklassen $\begin{eqnarray*} x+km'\bmod m \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,\ldots,g-1 \end{eqnarray*}$ .

16.06.2018, 17:37

georg2000

Auf diesen Beitrag antworten »

Verstehe , das kommt ca auf das selbe wie :
wenn ich weiß das die Lösungsmenge von $\begin{eqnarray*} ax_0-my_0=b \end{eqnarray*}$ gleich $\begin{eqnarray*} \lbrace x_0+ km/g,y_0 +ka/g |k \in Z \rbrace \end{eqnarray*}$
Man sucht die Anzahl der LÖsungen für die x im Restsystem von $\begin{eqnarray*} \lbrace x0,x0+1,..,x0+(m-1) \rbrace \end{eqnarray*}$ mod m liegt.
welches genau dann der Fall ist wenn $\begin{eqnarray*} x \in \lbrace x0+km/g | k \in \lbrace 0,1,..,g-1 \rbrace \rbrace \end{eqnarray*}$ welches g Stücke sind .

Neue Frage »

Antworten »

Diophantische Gleichung

Verwandte Themen