Lineare Diophantische Gleichungen

(Linear Diophantine equations)

 

(Stand: Mail 2007, © Axel Wagner)

Hinweise

Diese Materialien entstehen im Rahmen des Schulversuchs Informatik in der Sekundarstufe I

Am Saarpfalz-Gymnasium Homburg und am Albert-Einstein-Gymnasium Völklingen startet ab dem Schuljahr 2005/06 ein Informatikzweig
mit 5 Unterrichtsstunden in Klasse 8 und jeweils 4 Unterrichtsstunden in den Klassen 9 und 10.

Die Inhalte stammen aus folgenden Bereichen: Grundlagen, Zahlensysteme, Teilbarkeit, Euklidischer Algorithmus und Vielfachsummen, diophantische Gleichungen, Kongruenzrechnung, Gruppen (diskrete Mathematik), Programmieren, einfache Verschlüsselungsverfahren und Robotik.

Rückmeldungen bitte an    awainf(at)saarpfalz-gymnasium.de

 

 

Quellen/Links

http://www.zum.de/Faecher/Materialien/dorner/manuskripthtml/index.html

http://www.gap-system.org/~history/

http://www.zahlenjagd.at

 

Porträt: Diophant von Alexandrien

Aufgabe
Es stehen als Münzen 2Cent-Stücke und 5Cent-Stücke zur Verfügung. Wie viele verschiedene Möglichkeiten gibt es, daraus einen Betrag von 1€ zusammenzustellen?

Hausaufgabe: Mit 5 Cent und 10 Cent (5 Cent und 20 Cent)

x = Anzahl der 2Cent-Stücke und     0 <= x <= 50
y = Anzahl der 5Cent-Stücke und     0 <= y <= 20

2x + 5y = 100

Gesucht: Alle ganzzahligen Lösungen >=0 (11 Lösungen)

Lösungen erraten lassen & in ein Koordinatensystem eintragen lassen.
x-Achse: 1 entspricht 0,5cm;    y-Achse: 1 entspricht 0,5 cm

 

Erstellen des Diagramms mit OpenOffice
A
B
1

0

20
2

1

*
3

2

*
4

3

*
5

4

*
6

5

18
7

6

*
8

7

*
9

8

*
10

9

*
11

10

16
12

11

*

Die Formel in Spalte B lautet (Zeile 1):      =WENN((GANZZAHL(-2/5*A1+20)=-2/5*A1+20);-2/5*A1+20;"*")

 

Eigenschaften:

 

Definition
Lineare diophantische Gleichungen haben die Form ax + by = c mit a, b, c ∈ Z

Die gesuchten Lösungen sind Paare (x; y) ∈ Z2

Das Schaubild einer diophantischen Gleichung besteht aus ganzzahligen Gitterpunkten ∈ Z2, die auf einer Geraden liegen.

Auflösen nach y liefert die Gleichung einer Geraden:    y = -2/5x + 20

 

Weitere Beispiele    Bestimme zeichnerisch ganzzahlige Lösungen

x + 5y = 12 --> y = -1/5x + 12/5

x + 5y = 24 --> y = -1/5x + 48/10

1x - 1y = 7 --> L= { (8; 1), (9; 2), (10; 3), ......}

x + 2y = 1

 


Lösung einer diophantischen Gleichung mittels Vielfachsumme

Da für die Gleichung 2x + 7y = 1    der ggT(2 ,7) = 1 ist, existiert eine Vielfachsumme:

2*4 + 7*(-1) = 1

Welchen Rest lässt die linke Seite bei der Divisionszahl 7?

Es folgt: 2*4 ≡ 1 mod 7, d.h. 4 ist modulares Inverses zur 2 (modulo 7).


Aufgaben
Bestimme mit Hilfe des Berlekamp-Algorithmus Lösungen zu
ax + ny = 1 und zeige, dass ax ≡ 1 mod n


(a) 2x -5y = 1    (b) 4x +10y = 1       (c)       3x +9y = 1                    Warum existieren für (b) und (c) keine Lösungen?



Satz
Die Gleichung ax + ny = 1 ist lösbar  genau dann, wenn   ggT(a; n) = 1

Beweis

"-->"     Seien a' und b' Lösungen von ax + ny = 1 (*)

Für d = ggT(a; b) folgt d | ax + ny und damit gilt d | 1.
Dies ist aber nur für d = 1 möglich.


"<--"    Nach dem Berlekamp-Algorithmus gilt:    Es gibt a' und n' aus Z mit aa' + nn' = 1, d.h. (*) ist lösbar!

 

Wir suchen alle Lösungen

Beispiel: 5x + 16n = 1      (x0; y0) = (-3; 1)    ,


dann sind auch (x0 + kn; y0 - ka), k aus Z, Lösungen (*)

Sind dies auch alle Lösungen?     Ja!

Begründung

Ist (x1; y1) eine weitere Lösung, dann folgt:

ax1 + ny1 = 1 und natürlich auch ax0 + ny0 = 1.


Gleichsetzen der beiden rechten Seiten liefert

ax1 + ny1 = ax0 + ny0

a(x1 - x0) = n(y0 - y1)

bzw. (x1 - x0) / (y0 - y1) = n/a

Wegen ggT(a; n) =1 steht rechts ein gekürzter Bruch.

Daraus folgt: (x1 - x0) = k*n und (y0 - y1) = k*a mit k ∈ Z


Wir erhalten also alle Lösungen der Gleichung (*): x1 = x0 + kn und y1 = y0 - ka, k ∈ Z


Beispiel
Finde alle Lösungen von 5x+16n = 10    (*)

Das 10-fache der Lösung (x0 ; y0) der Gleichung 5x + 16n = 1 muss die Gleichung (*) lösen,
d.h.

10* (x0; y0) = (-30; 10)

Probe: -30*5 + 16*10 = 10

Alle Lösungen von 5x + 16n = 10 haben die Form (-30 + k*16; 10 - k*5).

 


Zusammenfassung
Gilt ggT(a ; n) = 1, so findet man alle Lösungen der Gleichung ax + ny = c wie folgt:

  1. Bestimme mit Hilfe des BA eine Lösung (x0; y0 ) der Gleichung ax + ny = 1
  2. Multipliziere diese mit c:    c*(x0; y0 ) = (c*x0; c*y0 )
  3. Bilde alle Lösungen: (c*x0 + kn ; c*y0 - ka) mit k ∈ Z



Weitere Beispiele

1x + 5n = 1          2x + 5n = 1                3x + 5n = 1              4x + 5n = 1

3x + 6y = 5          3x + 6y = 6                4x + 8y = 11          12x + 8y = 16 --> geteilt durch 4: 3x + 2y = 4

 

 

Die Ergebnisse führen zu folgendem Satz :

Es sind a, b, c ∈ N

die Gleichung     ax + by = c ist lösbar
genau dann wenn
die Zahl c ist ein Vielfaches von d = ggT(a , b)


Beweis

" ⇐" c ist ein Vielfaches von d:   c = d*c'
Nach dem BA gilt: Es gibt a' und b' (b' aus Z) mit aa' + bb' = d

Nach Multiplikation mit c' folgt:    a(c'a') + b(c'b') = c'd = c


"⇒" Seien a' und b' Lösungen von ax + by = c (*)
Wegen d = ggT(a; b) folgt:     d | ax + by     und damit gilt d | c

 

Ein JAVA-Applet zur Lösung linearer diophantischer Gleichungen

Das Applet wurde mit Eclipse 3.1, dem Designer Jigloo GUI Builder und Java5 entwickelt.

 

 

Informatik Sek. 1