Teilbarkeit für ganze Zahlen: ∃d, das a und b teilt, aber nicht c ==> ax+by=c hat keine ganzzahlige Lösungen x und y.

Question

Behauptung:∃

Seien a,b und c ganze Zahlen und angenommen es gibt ein d, das a und b teilt, aber c nicht teilt. dann hat die Gleichung ax+by=c keine ganzzahligen Lösung x und y.

Soll ich beweisen.

Answer 1

Wenn d a bzw. b teilt, lassen sich a und b darstellen als: \(a=j\cdot d, b=k\cdot d, j,k\in\mathbb{Z}\).

c lässt sich schreiben, als \(c=l\cdot d+m, d\in\mathbb{Z}, 0<m<d\).

Angenommen, es gibt Lösungen \(x, y\in\mathbb{Z}\).

Dann gilt: \(ax+by=c\Rightarrow jdx+kdy=ld+m\)

Betrachtet man diese Gleichung modulo d, erhält man: \(0\equiv m\text{ mod d}.\)

Wegen \(0<m<d\) und damit \(m\not\equiv 0\text{ mod d}\) ergibt sich ein Widerspruch. Also war die Annahme falsch, und es gibt keine ganzzahligen Lösungen x,y.

Answer 2

Diese Behauptung soll wohl bewiesen werden, nicht wahr?

 

Widerspruchsbeweis ("reductio ad absurdum"):

Voraussetzung: a , b, c und d sind ganze Zahlen und d teilt a und d teilt b, aber d teilt nicht c.

 

Wenn d teilt a und d teilt b gilt,  dann muss es zwei ganze Zahlen m und n geben, sodass gilt:

a = m * d und b = n * d

Dann:

a x + b y = c

<=> m * d * x + n * d * y  = c 

<=> m * x + n * y = ( c / d ) 

 

Nimmt man nun an, es gäbe ganzzahlige x und y, die diese Gleichung lösen, dann ist

m * x ganzzahlig und auch n * y ganzzahlig.

Dann aber muss auch deren Summe c / d ganzzahlig sein und daraus folgt d teilt c.

Das aber ist ein Widerspruch zur Voraussetzung, nach der gilt: d teilt nicht c

Also ist die Annahme, dass es ganzzahlige x und y gibt, die die gegebene Gleichung lösen, falsch. Daher gilt die logische Negation dieser Aussage, nämlich, dass es keine solchen x und y gibt, sondern dass entweder x oder y oder beide nicht ganzzahlig sind. Und das war zu beweisen.