GYMNASIUM KLEINE BURG

FACHARBEIT

im Leistungskurs:

Mathematik

Thema:

Lineare diophantische Gleichungen

Verfasser: Jan Stellet

Themenausgabe: 08.02.2006

Abgabetermin: 22.03.2006

---

Inhaltsverzeichnis

1 Einleitung 3

2 Historische Gesichtspunkte 3

3 Der euklidische Algorithmus 5

3.1 Division mit Rest 5

3.2 Der euklidische Algorithmus 6

3.3 Das Lemma von Bachet 8

3.4 Die Darstellung des ggT als Linearkombination 9

4 Lineare diophantische Gleichungen 11

4.1 Gleichungen mit einer Unbekannten 11

4.2 Gleichungen mit zwei Unbekannten 12

4.2.1 Kriterium für die Existenz ganzzahliger Lösungen 12

4.2.2 Auffinden einzelner Lösungen 12

4.2.3 Bestimmung aller Lösungen 13

4.2.4 Lösungen in den natürlichen Zahlen 14

4.3 Gleichungen mit mehr als zwei Unbekannten 15

5 Ergebnisse 16

Literaturverzeichnis 17

- 2 -

---

1 Einleitung

Seit mehr als 2.500 Jahren befassen sich Mathematiker mit dem Problem

des Findens von Lösungen zu einer Gleichung, welche nur aus einer be-

stimmten Zahlenmengen stammen. Diese Facharbeit soll einen Teil hiervon,

die linearen diophantischen Gleichungen, behandeln und zugehörige Aspek-

te beleuchten. Dies soll mit dem Ziel geschehen, Auflösungsstrategien nicht

nur vorzustellen, sondern ihre Herkunft zu ergründen. Aus diesem Grund

liegt der Fokus des ersten der beiden Hauptkapitel auf theoretischen Grund-

lagen der Teilbarkeitslehre, im zweiten auf ihrer Anwendung. Zunächst soll

jedoch kurz auf die für das Thema prägenden Namen Diophant und Euklid

eingegangen werden. Persönlicher Reiz der Themenstellung ist das niedrige

Einstiegsniveau durch die einfache Struktur der Gleichungen verbunden mit

der beliebig steigerbaren Komplexität der Vertiefungen. Die Grenze soll

hierbei nach dem Auffinden einzelner Lösungen zu Gleichungen mit belie-

big vielen Unbekannten gezogen werden, die Beschreibung der Gesamtheit

aller Lösungen in den ganzen oder natürlichen Zahlen entfällt.

2 Historische Gesichtspunkte

Diophantos von Alexandria ist einer der bedeutendsten Mathematiker der

Antike. Zwar ist nur wenig über das Leben des griechischen Mathematikers

bekannt und die Schätzung seiner Lebensdaten von ca. 200-280 v. Chr. ba-

siert auf der Erwähnung älterer Mathematiker in seinen Arbeiten und nach-

folgenden Zitaten dieser, doch prägen seine Erkenntnisse die Geschichte der

Mathematik in hohem Maße. Diophant lebte im ägyptischen Alexandria,

jahrhundertelang das wissenschaftliche Zentrum der Antike.1

Die ,,Arithmetik" (griech.: ist sein Hauptwerk und markiert eine

bedeutende Entwicklung der Algebra, jenem Teilgebiet der Mathematik, un-

ter welchem man die formale Auflösung algebraischer Gleichungen ver-

steht. Diophant schlug dort ein neues Kapitel in der griechischen Mathema-

tik auf, indem er sich darauf konzentrierte bestimmte und unbestimmte Glei-

chungen mit bis zu sechs Unbekannten ohne Rückgriff auf geometrische

1 Informationen entnommen aus: Bundschuh, Peter: Einführung in die Zahlentheorie S. 28.

- 3 -

---

Überlegungen zu lösen. Statt geometrischer Algebra wird dies auch als ech-

te Algebra bezeichnet. Die von ihm benutzte algebraische Bezeichnungs-

weise wird als synkopiert (verkürzt) bezeichnet und gilt als Zwischenschritt

von einer rein verbalen zu einer vollständig symbolischen Algebra. Die

,,Arithmetik" ist der einzige bekannte umfassende Text zur Algebra und

Arithmetik aus der griechischen Antike und stellt gleichzeitig das erste

große, ausschließlich zahlentheoretischen Problemen gewidmete Werk dar.

Von den dreizehn Büchern der in griechischer Sprache verfassten ,,Arithme-

tik" waren bis vor einigen Jahrzehnten nur sechs2 bekannt, in den 70er Jah-

ren fand man vier3 weitere, in arabische Sprache übersetzte Bände.4

Euklid von Alexandria (ca. 365-300 v. Chr.) war ebenfalls ein bedeutender

griechischer Mathematiker, welcher auch heute die Sprache der modernen

Mathematik prägt (Bsp.: euklidische Ringe, euklidische Räume u. v. m.). In

seinem berühmten Hauptwerk ,,Elemente" (griech.: ) fasste er ma-

thematisches Wissen seiner Zeit zusammen, damit es als Lehrwerk an der

Akademie des Platon verwendet werden konnte. Auch dienten die

,,Elemente" Euklid als Fundament für tiefer gehende mathematische Unter-

suchungen. Mindestens drei vorherige Verfasser ähnlicher Werke sind be-

kannt, diese sind jedoch nicht erhalten. Euklid wird nachgesagt sie als

Grundlage genommen und erweitert sowie verbessert zu haben. Insgesamt

setzen sich die ,,Elemente" aus dreizehn Büchern zusammen. In den ersten

sechs Bänden werden Erkenntnisse aus dem Bereich der Geometrie, in den

Büchern sieben bis neun der Zahlentheorie und in Kapitel elf bis dreizehn

der Stereometrie behandelt.5

Euklid führte Eigenschaften von ganzen Zahlen und geometrischen Objek-

ten auf eine Menge von Elementaraussagen (Axiome) zurück, was der

Axiomatisierung in der modernen Mathematik ähnelt.

2 Übersetzung und Kommentierung: Czwalina, A.: Arithmetik des Diophant aus Alexan-

dria. Göttingen: Vandenhoeck-Ruprecht 1952.

3 Sesiano, J.: Books IV to VII of Diophantus′ Arithmetica: In the Arabic Translation At-

tributed to Qusta Ibn Luqa. New York: Springer 1982.

4 Informationen entnommen aus: Mankiewicz, Richard: Zeitreise der Mathematik S. 46.

5 Informationen entnommen aus: Schreiber, Peter: Euklid S. 5; 32-37.

- 4 -

---

3 Der euklidische Algorithmus

Der euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten

gemeinsamen Teilers (ggT) zweier Zahlen. Er wird von Euklid von Alexan-

dria im Buch VII seines Hauptwerks ,,Elemente" vollkommen allgemein be-

schrieben. Der französische Mathematiker Bachet de Mézinac (1581-1638)

führte das Verfahren erstmals in Europa ein.6 Auf seine bedeutende Folge-

rung hinsichtlich des euklidischen Algorithmus, das Lemma von Bachet,

wird in Kapitel 3.3 eingegangen. Da der euklidische Algorithmus eine

wiederholte Division mit Rest darstellt, soll zunächst diese erläutert werden.

3.1 Division mit Rest

Geht die Division zweier ganzer Zahlen

a ,b

mit

b

0 nicht mit Rest 0

auf (man schreibt auch

a

b

im Gegensatz zu

a

b

für aufgehende Divisi-

on), lautet sie in der Schreibweise7 des Divisionsalgorithmus wie folgt:

a

=

qb

r ; q , r

,

0

r

b

.

Beispiel:

15

:

4 entspricht 15=343 .

Hierbei ist

q

ein ganzer Quotient von

a

und

r

der auftretende Rest.8 Es

sollen nun Existenz und Eindeutigkeit dieser Darstellung bewiesen werden.

Beweis der Existenz:

9 Der Rest von

a :b

ist die kleinstmögliche natürliche

Zahl

r

=

a

-

qb

0

; q

. Für

a

0 und

q

=0 ist die Forderung

a

-

qb

0 erfüllt. Ist hingegen

a

0 , so kann man ein

m

0 mit

m

b

a

bestimmen, damit für

q

=-

m

gilt: -

q

b

a

=-

a

, woraus

a

-

qb

0

folgt. Die Menge aller Reste

R

={

z

z

=

a

-

qb

0

; q

} ist damit nicht

leer und es existiert ein kleinstes Element

r

aus dieser Menge. Um zu

zeigen, dass

r

b

gilt, formt man

r

-

b

durch Einsetzen von

r

=

a

-

qb

um

zu

a

-

qb

-

b

und damit

a

-

b

q

1 . Da

b

0 ist, muss

a

-

b

q

1

a

-

qb

sein, denn für

b

0 ist

b

q

1

qb

. Weil

r

jedoch

das durch ein bestimmtes ganzzahliges

q

mittels

r

=

a

-

qb

definierte

kleinstes positives Element aus der Menge ist, kann

a

-

b

q

10 nicht

gelten. Denn andernfalls würde ein kleineres Element aus

R

als

r

existie-

ren. Somit resultiert, dass

r

-

b

0 ist und damit

r

b

.

6 Informationen entnommen aus: Bundschuh, Peter: Einführung in die Zahlentheorie S. 23.

7 Dies entspricht in der aus der Schule bekannten Notation: ,,a geteilt durch b = q Rest r".

8 Vgl. für diesen Abschnitt: Rose, H. E.: A Course in Number Theory S. 2.

9 Vgl.: Schreiber, A.: Einführung in die Mathematik, Kapitel 4 ,,Teilbarkeit" S. 1-4.

- 5 -

---

Beweis der Eindeutigkeit:

10

Um die Eindeutigkeit zu

beweisen, wählt man

je zwei verschiedene

q

und

r

:

a

=

q b

r

b

r

1

1 und

a

=

q

2

2 mit

0

r

b

=

q

=

r

1,2

. Es soll gezeigt werden, dass

q

1

2 und

r

1

2 gilt, wobei

man annimmt, dass

r

r

1

2 ist. Denn dann gäbe es für dasselbe Zahlenpaar

a ,b

nur eine Möglichkeit der Darstellung und die Eindeutigkeit wäre be-

wiesen. Man subtrahiert beide Gleichungen voneinander und erhält:

a

-

a

=

q b

-

q b

r

-

r

1

2

1

2

0=

b

q

-

q

r

-

r

1

2

1

2

b

q

-

q

=

r

-

r

2

1

1

2 .

Es folgt damit, dass die Differenz

r

-

r

1

2 ein Vielfaches von

b

ist. Auf-

grund der Voraussetzung 0

r

-

r

b

1

2

schließt man weiterhin, dass

r

-

r

=0

-

q

=0

1

2

sein muss und erhält wegen

b

0 zudem, dass

q

2

1

ist.

Im Folgenden wird die Verwendung der auch als Divisionsalgorithmus be-

zeichneten Darstellung anhand des euklidischen Algorithmus demonstriert.

3.2 Der euklidische Algorithmus

Der euklidische Algorithmus ist ein Verfahren der Wechselwegnahme und

gehört zu den ältesten und wichtigsten Algorithmen der Mathematik. Er

dient der Bestimmung des gemeinsamen Maß zweier Größen, d. h. einer

Größe

d

,11 welche in beiden Größen aufgeht. Prinzipiell handelt es sich um

eine sukzessiv wiederholte Division mit Rest, bei der als Divisor der jeweils

aktuelle Rest und als Dividend der vorherige Rest gewählt werden.12 Die k-

te Zeile entspricht dann der Form:

r

=

q

r

r

; k

=0,1 ,2

,

...

n

k

k

1

k

1

k

2

.

Das Erreichen des Restes

r

=0

n

1

in der (n-1)ten Gleichung ist die Ab-

bruchbedingung des Algorithmus, der vorhergegangene Rest

rn

der ge-

suchte größte gemeinsame Teiler. Die Bestimmung des ggT mithilfe des eu-

klidischen Algorithmus soll nun im allgemeinen Fall für zwei natürliche

Zahlen

a ,b

a

b

13 und für das Beispiel 123, 90 gezeigt werden.

10 Vgl.: Schreiber, A.: Einführung in die Mathematik, Kapitel 4 ,,Teilbarkeit" S. 1-4.

11 Eine weitere gängige Schreibweise für d=ggT(a,b) ist: (a,b).

12 Schreiber, A.: Einführung in die Mathematik, Kapitel 4 ,,Teilbarkeit" S. 5.

13 Da ggT(a,b)=ggT(|a|,|b|) und ggT(a,a)=a ist, genügt die Betrachtung von a>b>0.

- 6 -

---

r

=

a

=

q b

r

0

1

2

123=19033

r

=

b

=

q r

r

90=23324

1

2 2

3

r

=

q r

r

33=1249

2

3 3

4

24=296

r

=

q

r

r

n

-2

n

-1

n

-1

n

9=163

r

=

q r

n

-1

n n

6=23

Hierbei entspricht der letzte nicht verschwindende Rest

r n

bzw. 3 dem

größten gemeinsamen Teiler beider Zahlen.

Beweis:14

Der Beweis gliedert sich in drei Abschnitte, in denen die Aspekte der Mono-

tonie von der Folge der Reste, die gemeinsamen Teiler zweier aufeinander

folgender Paare von Resten wie z. B.

r , r

, r

2

3 und

r

3

4 sowie die Frage, ob

der letzte nicht verschwindende Rest

r n

der

ggT

a , b

ist, getrennt be-

handelt werden.

a)

Monotonie der Folge von Resten:

Die auftretenden Folge der Reste

r , r , r ,

...

, r

0

1

2

n

ist streng monoton fallend, da der Divisor

r k

1 in der

k-ten Zeile des Verfahrens kleiner ist als der Dividend

r k

. Für

k

=0 ist

das die vorausgesetzte Ungleichung

b

a

. Ist

k

0 , ergibt sich dies di-

rekt aus der Division mit Rest:

a

=

qb

r ; b

r

0 . Das heißt, dass der

entstehende Rest immer kleiner ist als der Divisor. Damit besitzt die

streng monoton fallende Folge natürlicher Zahlen nur endlich viele von

0 verschiedene Glieder:

r

r

r

...

r

r

=0

0

1

2

n

n

1

.

b)

Gemeinsame Teiler von Restepaaren:

Bei Betrachtung der k-ten Zeile

r

=

q

r

r

k

k

1

k

1

k

2 stellt man fest, dass offensichtlich für eine beliebige

Zahl

t

t

r

t

r

t

r

k

k

1 nur dann gilt, wenn

t

rk

1

k

2 . Dies bedeu-

tet, dass ein gemeinsamer Teiler

t

von

r , r

k

k

1 nur dann existiert,

wenn er auch gemeinsamer Teiler von

r

, r

k

1

k

ist. Ausgehend von

k

=0 bis

k

=

n

1 kann somit gefolgert werden, dass

a ,b

und

r , r

n

n

1 dieselben gemeinsamen Teiler besitzen. Da nach a) jedoch

r

=0

n

1

ist, sind alle Teiler von

r n

die gemeinsamen Teiler von

a ,b

.

14 Vgl.: Schreiber, A.: Einführung in die Mathematik, Kapitel 4 ,,Teilbarkeit" S. 5-6.

- 7 -

---

c)

Größter gemeinsamer Teiler:

Sei

t

irgendein gemeinsamer Teiler von

a ,b

, so ist

t

auch Teiler von

r

t

n

. Daraus folgt, dass

r n

ist und so-

mit

r n

der größte aller gemeinsamen Teiler von

a ,b

ist.

Die Bestimmung des ggT mithilfe des euklidischen Algorithmus ist ins-

besondere bei großen Zahlen ein deutlich schnelleres Verfahren als die Me-

thode der Primfaktorzerlegung. Die Anzahl

l

der dabei durchzuführenden

Divisionsgleichungen ist gegeben durch:

l

log

a ,

= 15 1,61 .15

2

3.3 Das Lemma von Bachet

Der französische Mathematiker Bachet de Mézinac folgerte 1624 in der 2.

Ausgabe seines Werkes ,,Problèmes plaisants et délectables" über den ggT:

Der größte gemeinsame Teiler d zweier natürlicher Zahlen a und b

ist als Vielfachensumme (Linearkombination) von a und b darstellbar,

d. h. es gibt ganze Zahlen x , y für die gilt: d

=

ax

by .16

Beweis:17

Um Bachets Satz zu beweisen, betrachtet man zunächst alle für

beliebige

x , y

möglichen Linearkombinationen. Diese Menge

{

ax

by

} enthält sowohl positive als auch negative ganzzahlige Werte. Nun

sei das kleinste positive Element

k

der Menge bestimmt durch:

k

=

ax

by

0

0 . Zu zeigen ist nun, dass

k

sowohl

a

als auch

b

teilt. Für

ersteres wird dies durch einen indirekten Beweis (d. h.: man nimmt an, dass

k

a

gilt und ein Widerspruch ergibt sich) erledigt, der zweite Fall kann

analog dazu erfolgen. Nach der Annahme geht

k

in

a

nicht auf, weshalb

man die Darstellung der Division mit Rest anwenden kann:

a

=

qk

r ; q , r

,

0

r

k

.

r

=

a

-

qk

. Setzt man

ax

by

0

0 für

k

ein, so erhält man:

r

=

a

-

q

ax

by

0

0

r

=

a

-

qax

-

qby

0

0

r

=

a

1-

qx

b

-

qy

0

0

.

x

y

1

1

Nun ist erkennbar, dass der Rest

r

Element der Menge {

ax

by

} ist, ge-

15 Vgl.: Wiesenbauer, Johann: AKDIS Zahlentheorie und Anwendung S. 4 Satz 1.8.

16 Aus: Schreiber, A.: Einführung in die Mathematik, Kapitel 4 ,,Teilbarkeit" S. 6.

17 Vgl.: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 6 Satz 1.3.

- 8 -

---

bildet mit den gekennzeichneten

x , y

1

1 . Da der Rest

r

jedoch kleiner als

der Divisor

k

ist, ergibt sich ein Widerspruch, denn

k

ist per Voraus-

setzung das kleinste Element der Menge. Des Weiteren können, sofern

d

der größte gemeinsame Teiler von

a

und

b

ist, diese mit

A , B

in der

Form

a

=

Ad

und

b

=

Bd

geschrieben werden, womit für

k

folgt:

k

=

ax

by

=

Adx

Bdy

=

d

Ax

By

0

0

0

0

0

0 .

Man erkennt sofort, dass

d

k

gelten muss, da der Inhalt der Klammer in je-

dem Fall einen ganzzahligen Wert annimmt. Aus der Division zweier natür-

licher Zahlen geht weiterhin hervor, dass der Divisor immer kleiner oder

gleich dem Dividenden ist. Überträgt man dies auf

k :d

, so folgt:

k

d

.

Weil

d

aber der größte gemeinsame Teiler ist, ist der Fall

k

d

unmöglich

und es gilt:

k

=

d

=

ax

by

0

0 .

3.4 Die Darstellung des ggT als Linearkombination

Der ggT als letzter positiver Rest im euklidischen Algorithmus soll nun ent-

sprechend dem Lemma von Bachet als Linearkombination geschrieben

werden. Hierzu eliminiert man die Reste

r , r ,

..

, r

, r

2

3

n

-2

n

-1 aus der Glei-

chungskette des Algorithmus. Für

r

=

a

=

b

0

und

r

1

ist sofort ersichtlich:

r

=1

a

0

b

0

r

=0

a

1

b

1

Die weiteren Reste können nun folgendermaßen geschrieben werden:

r

=

a

b

-

q

=

q b

r

2

1 , denn

a

=

r

0

1

2 ;

r

=

a

-

q

b

1

q q

=

r

-

q r

=

a

-

q b

=

b

3

2

1

2 , da

r

3

1

2 2 sowie

r

2

1

und

r

1

.

Dieses Vorgehen kann sukzessive für die folgenden

r , r ,

...

, r

, r

4

5

n

-1

n

fort-

gesetzt werden, so dass man letztendlich erhält:

r

=

d

=

a

...

b

...

n

Der Inhalt der Klammern stellt hierbei eine Lösung der Gleichung

d

=

ax

by

dar und erlaubt somit eine Darstellung von

d

=

ggT

a , b

als

Linearkombination von

a

und

b

. 18

Im Folgenden soll eine weitere Möglichkeit, der erweiterte euklidische Al-

gorithmus (auch Berlekamp-Algorithmus genannt), gezeigt werden, um die

18 Vgl.: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 11-12 Satz 1.11.

- 9 -

---

Linearkombination effektiv zu bestimmen. Aus dem Verlauf des eu-

klidischen Algorithmus stammen hierbei die auftretenden

qi

, sowie der In-

dex

n

des letzten positiven Rests

r n

. Gesucht werden nun die

n

-1

,

n

-1 ,

welche als Koeffizienten von

a

und

b

die Linearkombination bilden.

Diese

i ,

i

werden dabei durch zwei rekursiv definierte Folgen gebildet:

0=0,

i

1=

i ,

0=1,

i

1=

i

-

qn

-1-

i

i ; i

=0,1,2

,

...

,n

-2,

n

-1 . Ein-

gesetzt wird nach der Formel

i

rn

-1-

i

i

rn

-

i

=

rn

, was im Folgenden für

die ersten Werte für

i

getan wird.

i

=0 :

0

rn

-10

rn

=

rn

0

r

1

r

=

r

n

-1

n

n

i

=1 :

1

rn

-21

rn

-1=

rn

0

rn

-20-

qn

-1 0

rn

-1=

rn

1

r

-

q

r

=

r

n

-2

n

-1

n

-1

n

i

=2 :

2

rn

-32

rn

-2=

rn

1

rn

-31-

qn

-2 1

rn

-2=

rn

0-

qn

-1 0

rn

-3 0-

qn

-2 1

rn

-2=

rn

-

qn

-1

rn

-31-

qn

-2 1

rn

-2=

rn

Die Richtigkeit der ersten beiden Fälle ist sofort offensichtlich. Man kann so

bis

i

=

n

-1 weiter fortfahren und erhält dann die Linearkombination mit

n

-1

r

0

n

-1

r

1=

n

-1

a

n

-1

b

=

rn

=

d

.19

Diese Methode findet vor allem in Computer-Programmen20 z. B. für die

Kryptographie21 Anwendung, wo sie zur Verschlüsselung von Daten dient.

Ein weiterer Aspekt, welcher beim Umformen der Gleichungskette des eu-

klidischen Algorithmus auftritt und ebenfalls die Bildung der Linearkombi-

nation ermöglicht, sind endliche Kettenbrüche. Sie entstehen, wenn man die

a

erste Gleichung im euklidischen Algorithmus nach

umformt und die

b

r

a

=

q

1

Brüche der Form

k

-1 , welche im Nenner des Ausdrucks

b

1

b

vor-

r k

r

2

19 Vgl. für diesen Abschnitt: Bundschuh, Peter: Einführung in die Zahlentheorie S. 31-32;

Wiesenbauer, Johann: AKDIS Zahlentheorie und Anwendung S. 3-4

20 Siehe für eine Umsetzung in der Programmiersprache C:

http://www.lexiwise.de/info_skripte/quellcodes/erweiterter_euklid.c.

21 Siehe auch zur Verwendung in der Kryptographie: http://www.wiwi.uni-

bielefeld.de/StatCompSci/lehre/material_spezifisch/statalg00/rsa/rsa.html.

- 10 -

---

liegen, jeweils durch die entsprechend umgeformte folgende Gleichung im

euklidischen Algorithmus ersetzt. Aufgrund der Komplexität dieses Themas

sei hier anstatt einer genaueren Betrachtung nur der Verweis auf 22 gegeben.

4 Lineare diophantische Gleichungen

Unter diophantischen Gleichungen versteht man algebraische Gleichungen,

von denen ausschließlich Lösungen in einer bestimmten Zahlenmenge wie

z. B. den ganzen Zahlen gesucht werden.23 Viele bedeutende Mathema-

tiker wie Euklid, Pythagoras, oder Pierre de Fermat befassten sich mit

diesem Thema der Zahlentheorie . Benannt werden sie zu Ehren des grie-

chischen Mathematikers Diophant von Alexandria, welcher sich um 250 v.

Chr. in seinem Werk ,,Arithmetika" mit ihnen befasste. Vollständig geklärt

ist das Problem nur für Gleichungen bis zum zweiten Grad und somit fehlen

allgemeine Methoden.24 Abgesehen von theoretischen Interessen kommen

solche Gleichungen bisweilen auch in physikalischen und chemischen Zu-

sammenhängen vor.25 Hier sollen nun lineare diophantische Gleichungen

mit ganzzahligen Koeffizienten ungleich Null behandelt werden. Da eine

solche Gleichung in jedem Fall unendlich viele Lösungen in den rationalen

Zahlen hat, werden nur Lösungen in den Mengen der ganzen Zahlen

und der natürlichen Zahlen betrachtet. Die allgemeine Form einer sol-

chen Gleichung lautet:

a

1

x

1

a

2

x

2...

ak

-1

xk

-1

ak xk

=

c ; ai , c

4.1 Gleichungen mit einer Unbekannten

Jede lineare Gleichung mit nur einer Variablen und ganzzahligem Koeffizi-

enten lässt sich durch Äquivalenzumformung in die Form

a

1

x

1=

c ; c

bringen. Stellt man dies nach

x

=

c

1 um, so erhält man

x

1

a

. Es ist sofort

1

ersichtlich, dass nur dann eine ganzzahlige Lösung für

x

1 existieren kann,

wenn

a

1 in

c

restlos aufgeht. Ist das der Fall, so hat man die einzige Lö-

sung der Gleichung bereits durch den entsprechenden Quotienten gefunden.

22 Gelfond, A. O.: Die Auflösung von Gleichungen in ganzen Zahlen S. 11-17.

23 Informationen entnommen aus: Rose, H. E.: A Course in Number Theory S. 4.

24 Hilberts zehntes Problem - Wie kann man entscheiden, ob eine beliebige diophantische

Gleichung lösbar ist? 1970 zeigte Juri W. Matijassewitsch, dass dies nicht möglich ist.

25 Informationen aus: Gelfond, A. O.: Die Auflösung von Gleichungen in ganzen Zahlen S. 5-6.

- 11 -

---

Auch die Bedingung für die Existenz einer Lösung in den natürlichen Zah-

len ist offensichtlich: Sowohl

c

als auch

a

1 müssen entweder positive oder

negative ganze Zahlen sein, nur dann ist ihr Quotient größer als Null.26

4.2 Gleichungen mit zwei Unbekannten

Hierbei handelt es sich um den wichtigsten Fall, denn das Lösen aller wei-

teren Gleichungen mit mehr als zwei Variablen basiert auf der Zurück-

führung auf eine Gleichung mit zwei Unbestimmten.

4.2.1 Kriterium für die Existenz ganzzahliger Lösungen

Gegeben sei die lineare diophantische Gleichung

a

1

x

1

a

2

x

2=

c ; a

1

, a

2

, c

(1),

für welche ermittelt werden soll, ob ganzzahlige Lösungen existieren. Der

größte gemeinsame Teiler

d

=

ggT

a , a

1

2 teilt naturgemäß beide Koeffi-

zienten

a , a

1

2 . Dividiert man die gesamte Gleichung durch

d

, so können

ganzzahlige Werte für

x , x

1

2 nur dann existieren, wenn

c

d

gilt. Die An-

zahl aller möglichen Lösungen in ist dann unendlich groß. Angemerkt

sei, dass

c : d

bei

c

=0 immer Null ergibt und entsprechend jede Glei-

chung der Form

a x

a x

=0

1

1

2

2

in ganzen Zahlen lösbar ist.27

4.2.2 Auffinden einzelner Lösungen

Für das Finden von Zahlenpaaren

x

0

, y

0 , welche die Gleichung (1) auf-

lösen, bieten sich verschiedene Möglichkeiten an. Der triviale Fall liegt für

c

=0 vor: Man erkennt sofort, dass

x

=0,

y

=0

0

0

eine Lösung ist. Ist je-

doch

c

0 , eröffnen sich verschiedene Möglichkeiten:

Zum einen das systematische Einsetzen verschiedener ganzzahliger Zahlen-

paare, um so durch Ausprobieren bzw. ,,Ablesen" eine Lösung zu finden.

Beispiel:

Bei der Gleichung 11x -2x =1

=1,

y

=5

1

2

ist

x

0

0

offensichtlich.

Eine andere und insbesondere bei großen Zahlenwerten deutlich effektivere

Methode, die in jedem Fall eine ganzzahlige Lösung der Gleichung liefert,

soll nun gezeigt werden. Nach dem Lemma von Bachet gibt es zur Darstel-

lung des

ggT

a , a

1

2 die Linearkombination

a

1

x

a

2

y

=

d ;

x , y

.

26 Vgl. für diesen Abschnitt: Gelfond, A. O.: Die Auflösung von Gleichungen in ganzen Zahlen S. 7.

27 Vgl. für diesen Abschnitt: Bundschuh, Peter: Einführung in die Zahlentheorie S. 30.

- 12 -

---

Die Ähnlichkeit zur Gleichung (1) springt sofort ins Auge und nach Multi-

c

c

c

plikation mit

erhält man:

a

x

a

y

=

c

. So ist

x

=

c x , y

=

c y

d

1

d

2

d

0

d

0

d

eine Lösung der Gleichung (1).28 Es handelt sich aber nur um eine einzelne

(partikuläre) Lösung. Die Gesamtheit der unendlich vielen möglichen Lö-

sungen beschreibt man mit einem Parameter.

4.2.3 Bestimmung aller Lösungen

Voraussetzung für die Darstellung aller Lösungen ist zunächst die Kenntnis

einer einzelnen Lösung. Im weiteren Verlauf sei

r , s

eine beliebige und

x , y

0

0 eine bekannte Lösung zu (1). Es resultiert somit die Gleichung:

a r

a s

=

c

=

a x

a y

-

a x

-

a s

1

2

1 0

2

0

1

0

2

a r

-

a x

=-

a s

a y

1

1 0

2

2

0

a

r

-

x

=-

a

s

-

y

:d

=

ggT

a , b

1

0

2

0

a

a

1

r

-

x

=- 2

s

-

y

(2).

d

0

d

0

a

a

Da 1 sowie 2 teilerfremd29 sind und

s

-

y

d

d

0 einen ganzzahligen Wert

annimmt (denn per Voraussetzung sind

s , y

0 ), ist

r

-

x

0 ein Vielfaches

a

a

von 2 und

s

-

y

1 . Das führt zu der Darstellung

d

0 ein solches von

d

a

a

r

-

x

= 2

t ; t

sowie

s

-

y

= 1

u ; u

. Setzt man dies in (2) ein,

0

d

0

d

a

a

ergibt sich

u

=-

t

und man erhält damit

r

=

x

2

t

sowie

s

=

y

- 1

t

.30

0

d

0

d

Nun bleibt noch zu zeigen, dass jedes so mit einem beliebigen

t

0 erhal-

tene Zahlenpaar

r , s

0

0 auch eine Lösung der diophantischen Gleichung ist.

a

a

Beweis:31

Man setzt diese Lösung

r

=

x

2

t , s

=

y

- 1

t

in (1) ein:

0

0

d

0

0

0

d

0

a r

a s

=

c

1 0

2 0

a

a

a

x

2

t

a

y

- 1

t

=

c

1

0

d

0

2

0

d

0

a a

a a

a x

1 2

t

a y

- 1 2

t

=

c

1

0

d

0

2

0

d

0

a x

a y

=

c

1

0

2

0

.

Da

x , y

0

0 eine bekannte Lösung ist, wird die Gleichung gelöst. Damit ist

28 Vgl. für diesen Abschnitt: Bundschuh, Peter: Einführung in die Zahlentheorie S. 30.

29 Vgl.: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 8 Satz 1.7.

30 Vgl. für diesen Abschnitt: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 134.

31 Vgl.: Gelfond, A. O.: Die Auflösung von Gleichungen in ganzen Zahlen S. 10.

- 13 -

---

die Gesamtheit aller ganzzahligen Lösungen

r , s

der linearen diophantisch-

en Gleichung (1) mit dem als Lösung bekannten Zahlenpaar

x , y

0

0 und

a

a

dem Parameter

t

in der Form

r

=

x

2

t , s

=

y

- 1

t

gegeben. Für

0

d

0

d

den Fall

c

=0 folgt analog hierzu, dass alle Lösungen

r , s

durch

a

a

r

= 2

t , s

=- 1

t

gebildet werden, da

x

=0,

y

=0 bekanntermaßen eine

d

d

0

0

Lösung einer Gleichung der Form

a x

a x

=0

1 1

2

2

ist.

4.2.4 Lösungen in den natürlichen Zahlen32

Neben den ganzzahligen Lösungen in können auch die Lösungen in den

natürlichen Zahlen bestimmt werden. Vorausgesetzt wird für die zu be-

trachtende Gleichung (1), dass

a

1

, a

2

, c

sind. Um nur positive Werte

für die allgemeine ganzzahlige Lösung

r , s

zu erhalten, beschränkt man

t

.

a

a

r

=

x

2

t

0

s

=

y

- 1

t

0

0

d

0

d

a

a

2

t

-

x

y

1

t

d

0

0

d

d

t

-

d x

y

t

a

0

a

0

2

1

Da die Ungleichung -

d x

t

d y

a

0

a

0 auch für ein

t

erfüllt wird, ver-

2

1

wendet man die Gaußsche Klammerfunktion,33 um einen Wert für das größt-

und kleinstmögliche ganzzahlige

t

zu finden. Diese Funktion

f

x

=[

x

]

gibt für ein

x

die nächste ganze Zahl kleiner oder gleich

x

an. Zur Be-

stimmung von

tmin

muss der Wert dementsprechend zuvor um eins erhöht

werden und es resultiert:

t

=[-

d x

1]

, t

=[

d y

]=-[-

d y

1]

min

a

0

max

a

0

a

0

.

2

1

1

Die Tatsache, dass sowohl eine obere als auch eine untere Grenze für

t

be-

steht, legt nahe, dass es im Gegensatz zu den unendlich vielen Lösungen in

nur eine endliche Zahl hiervon in gibt. Um diese Anzahl

n

zu be-

stimmen, bildet man die Differenz von

tmax

und

tmin

und erhöht um eins:

n

=

t

­ t

1=-[-

d y

1]-[-

d x

1]1=-[-

d y

][-

d x

]1 .

max

min

a

0

a

0

a

0

a

0

1

2

1

2

Die letzte Umformung beruht auf der Tatsache,34 dass für

x

, y

32 Aus: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 135-136.

33 Vgl.: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 102-109.

34 Vgl.: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 102 Satz 4.1c.

- 14 -

---

[

x

y

]=[

x

]

y

ist. Da ferner gilt,35 dass [

x

][

y

][

x

y

][

x

][

y

]1

mit

x , y

ist, ergibt sich die folgende Ungleichung für

n

:

-[-

d y

-

d x

]1

n

-[-

d y

-

d x

]

a

0

a

0

a

0

a

0

1

2

1

2

-[-

d y a

-

d x a

]1

n

-[-

d y a

-

d x a

]

a a

0

2

a a

0

1

a a

0

2

a a

0

1

1 2

1

2

1

2

1

2

-[-

d

y a

x a

]1

n

-[-

d

y a

x a

]

a a

0 2

0

1

a a

0

2

0 1

.

1

2

1

2

Und da

x , y

x

a x

=

c

0

0 eine Lösung zu

a

1 1

2

2

ist:

-[-

dc

]-1

n

-[-

dc

]

a a

a a

.

1

2

1

2

Dies liefert zwei aufeinander folgende Werte für

n

, von denen eine der ge-

nauen Anzahl aller Lösungen der Gleichung in den natürlichen Zahlen ent-

spricht. Ferner folgt, dass, sofern das Lösbarkeitskriterium

c

d

erfüllt ist,

mindestens eine Lösung in existiert, wenn

dc

a a

1

2 ist, da andernfalls

0

dc

1

]0

a a

und somit

n

[

dc

a a

wäre.

1

2

1

2

4.3 Gleichungen mit mehr als zwei Unbekannten

Viele Aspekte des Lösens einer linearen diophantischen Gleichung mit den

k

2 Unbekannten

x , x ,

...

, x

, x

1

2

k

-1

k

, welche die allgemeine Form

a

1

x

1

a

2

x

2...

ak

-1

xk

-1

ak xk

=

c ai ,c

(3)

hat, lassen sich durch Zurückgriff auf die Gleichungen des Typs (1) mit

zwei Unbestimmten gewinnen. So erweitert man das Kriterium für die

Existenz ganzzahliger Lösungen auf

ggT

a , a ,

...

, a

, a

c

1

2

k

-1

k

, wobei die

Begründung analog zu 4.2.1 erfolgt.36

Um eine einzelne Lösung der Gleichung zu finden, verfährt man wie folgt:37

a) Man reduziert die Ausgangsgleichung (3) mit

k

Unbekannten auf

a x

a x

...

a

x

b y

=

c

, x ,

...

, x

, y

1

1

2

2

k

-2

k

-2

1

1

mit

k

-1 Variablen

x

1 2

k

-2

1 .

Hierzu setzt man

a

x

a x

=

b y

=

ggT

a

, a

k

-1

k

-1

k

k

1

1 und

b

1

k

-1

k

.

Dieses Vorgehen führt man weiter fort und es resultiert die Gleichung

a x

a x

...

a

x

b y

=

c

1

1

2

2

k

-3

k

-3

2

2

mit

k

-2 Unbestimmten, wobei

a

x

b y

=

b y

=

ggT

a

,b

k

-2

k

-2

1

1

2

2 und

b

2

k

-2

1 gesetzt werden.

35 Vgl.: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 102 Satz 4.1d.

36 Vgl.: Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 137.

37 Vgl.: Bundschuh, Peter: Einführung in die Zahlentheorie S. 33.

- 15 -

---

b) Nach

k

-2 Schritten erhält man schließlich die Reduktion von (3) auf

a x

b

y

=

c

, y

1 1

k

-2

k

-2

(4) mit den zwei Unbekannten

x

1

k

-2 , indem man

a x

b

y

=

b

y

=

ggT

a , b

2

2

k

-3

k

-3

k

-2

k

-2 (5) sowie

bk

-2

2

k

-3 setzt.

c) Durch die von Gleichung (4) auf bekannte Weise erhaltenen Werte für

x , y

1

k

-2 hat man nun zum einen bereits eine Lösung für

x

1 der Aus-

gangsgleichung (3), zum anderen kann man jedoch mit dem erlangten

Wert für

yk

-2 Gleichung (5) komplettieren und auflösen.

d) So ermöglicht die letzte Komponente

y

jeder nach diesem Schema

erhaltenen Lösung

x , y

i

k

-1-

i

die vollständige Aufstellung und Auflö-

sung der vorhergegangenen Gleichung der Form (5). Letztendlich erhält

man auf diese Weise Werte für alle

xi

der Ursprungsgleichung (3).

Die Darstellung der Gesamtheit aller Lösungen über eine gewisse Anzahl an

Parametern betreffend folgt an dieser Stelle aufgrund des Umfangs des The-

mas nur der Verweis auf 38 und 39.

5 Ergebnisse

Zusammengefasst wurden im Hauptteil folgende Inhalte behandelt: Ge-

schichtliche Hintergründe wurden kurz vorgestellt, elementare Aspekte der

Teilbarkeitslehre wurden aufgerollt und in Zusammenhängen zu wichtigen

Erkenntnissen wie dem Lemma von Bachet entwickelt. Anhand des Themas

der linearen diophantischen Gleichungen, welches durch Unterteilung in

Gleichungen mit einer, zwei und beliebig vielen Unbekannten logisch auf-

einander aufbaut, wurden die gewonnenen Methoden zu konkreten Werk-

zeugen. Wenngleich diese Erkenntnisse nur einen kleinen Teil des Themen-

komplexes der diophantischen Gleichungen repräsentieren, so sind sie doch

als Grundlage für weitergehende Vertiefungen hilfreich. Die hier nicht vor-

kommenden quadratischen diophantischen Gleichungen, deren wohl be-

kanntester Vertreter das pythagoreische Tripel

a

2

b

2=

c

2 ist, sind dabei

eine Möglichkeit. Abseits aller theoretischen Interessen kann die Bedeutung

des Auffindens von Lösungen nur aus den natürlichen oder ganzen Zahlen

38 Bundschuh, Peter: Einführung in die Zahlentheorie S. 33-35.

39 Niven, I.; Zuckermann, H. S.: Einführung in die Zahlentheorie S. 137-139.

- 16 -

---

auch daran gemessen werden, dass Zahlen aus diesen Mengen die wahr-

scheinlich am häufigsten im alltäglichen Leben anzutreffende Position

einnehmen und die Mathematik aus der Beschreibung von Mengen in eben

diesen alltäglichen Zusammenhängen entstanden ist.

Literaturverzeichnis

Bücher, Monographien

Bundschuh, Peter: Einführung in die Zahlentheorie.

5. Auflage. Berlin (u.a.): Springer 2002. Springer-Lehrbuch.

Frey, Gerhard: Elementare Zahlentheorie.

1. Auflage. Braunschweig/Wiesbaden: Friedr. Vieweg&Sohn 1984

Vieweg-Studium: Grundkurs Mathematik Nr. 56.

Gelfond, Aleksandr Osiporie: Die Auflösung von Gleichungen in ganzen

Zahlen (Diophantische Gleichungen).

4. Auflage. Berlin: Dt. Verlag der Wissenschaft 1968.

Mankiewicz, Richard: Zeitreise der Mathematik. Vom Ursprung der Zahlen

zur Chaostheorie. 1. Auflage. Köln: VGS 2000.

Niven, Ivan; Zuckermann, Herbert S.: Einführung in die Zahlentheorie.

3. Auflage. Mannheim: Bibliographisches Institut 1976.

B.I. Hochschultaschenbuch.

Rose, Harvey Ernest: A Course in Number Theory.

1. Auflage. Oxford: Clarendon Press 1988. Oxford Science publications.

Schreiber, Peter: Euklid.

1. Auflage. Leipzig: BSB Teubner 1987.

Biographien hervorragender Naturwissenschaftler, Techniker und Mediziner.

Internetquellen

Schreiber, Alfred (1996): Einführung in die Mathematik, Kapitel 4

,,Teilbarkeit" (PDF-Datei, erstellt am 29.03.2004). Internet: http://www.uni-

flensburg.de/mathe/zero/veranst/arithalgebra/schreiber/einfmath1996/4_teil

barkeit.pdf (Zugriff: 18.02.2006, 14:24)

Wiesenbauer, Johann (2005): AKDIS Zahlentheorie und Anwendungen

(PDF-Datei, erstellt am 4.04.2005).

Internet: http://www.algebra.tuwien.ac.at/institut/zthanw/ZthAnw1_1.pdf

(Zugriff: 7.03.2006, 18:38)

- 17 -

---