Beweis das diophantische Gleichung lösbar ist

Question

Aufgabe:

Gegeben sei die lineare diophantische Gleichung  ax - my = c mit a,m,c Element von Z (ganze Zahlen)

Beweisen sie ,dass die folgende Aussage wahr ist.

Die Gleichung ist für alle c Element Z (ganze Zahlen) lösbar, wenn es ein x' Element Zm mit a' × x' = 1' gibt.

Ich bräuchte mal eure Hilfe bei dieser Aufgabe, komme überhaupt nicht klar. Würde mich über jede Hilfe freuen!

PS: a' x' und 1' sollen Restklassen darstellen

Answer 1

Die Gleichung ist genau dann für alle ganzen Zahlen c lösbar, wenn sie für c = 1 lösbar ist. Ein Lösungspaar für die Gleichung mit 1 kann man einfach mit c multiplizieren und erhält ein Lösungspaar für die Gleichung mit c. Die Gleichung a*x - m*y = 1 kann man umschreiben zu a * x - 1 = m * y, und per Definition heißt dies, dass a * x und 1 kongruent sind modulo m. Oder eben, dass die Restklassen gleich sind: a' * x' = 1. Für konkrete teilerfremde Zahlen a und m findet man übrigens geeignete Zahlen x und y mit Hilfe des Euklidischen Algorithmus.

Comments

Supi, danke schön!