________________________________________________________________________________
Inhalt....: Berechnung des ggT und kgV
Kategorie.: Grundkurs
Mathematik: Zahlentheorie, Kryptographie
MuPAD.....: 3.0.0
Datum.....: 2004-03-31
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: igcd, igcdex, ilcm
________________________________________________________________________________
Berechnung des ggT und kgV
Dieses Arbeitsblatt ist Bestandteil des MuPAD Grundkurses.
Zu den elementarsten Algorithmen der Zahlentheorie und der Kryptographie
gehören die Berechnung des größten gemeinsamen Teilers durch den
Euklidischen Algorithmus. Hier sehen wir, wie man mit MuPAD den größten
gemeinsamen Teiler und das kleinste gemeinsame Vielfache von ganzen
Zahlen (und, ganz kurz am Rande, von Polynomen) berechnen kann.
Zur Berechnung des größten gemeinsamen Teilers (ggT) zweier ganzer
Zahlen steht in MuPAD die Funktion "igcd" (integer greatest common divisor)
bereit.
Die Funktion igcd erhält stets zwei Argumente: Eine ganze Zahl a und eine
ganze Zahl b, d.h. also ein Aufruf ist immer von der Form "igcd( a, b )". Als
Rückgabewert liefert uns die Funktion igcd den größten gemeinsamen Teiler
von a und b.
Einige kleine Beispiele verdeutlichen wie immer den Umgang mit dieser
neuen Funktion:
igcd(10, 3)
igcd(10, 4)
igcd(250, 20)
igcd(236236, 23889389218926)
Erinnern wir uns an den Euklidischen Algorithmus zur Berechnung des größten
gemeinsamen Teilers, so liefert dieser auch ganze Zahlen k und l, so dass ggT
( a, b ) = k * a + l * b gilt. Um den größten gemeinsamen Teiler und zusätzlich
die Zahlen k und l zu berechnen, kann die Funktion "igcdex" benutzt werden.
Die Funktion "igcdex" erhält stets zwei Argumente: Eine ganze Zahl a und eine
ganze Zahl b, d.h. also ein Aufruf ist immer von der Form "igcdex( a, b )". Als
Rückgabewert liefert uns die Funktion igcdex eine Sequenz von drei ganzen
Zahlen g, k, l. Dabei ist g der größte gemeinsame Teiler von a und b und k
und l erfüllen die oben beschriebene Gleichung, d.h. g = k * a + l * b. Auch hier
wieder einige Beispiele:
a:= 27: b:= 99:
igcdex(a, b)
Auf die einzelnen Zahlen der Sequenz greift man genauso zu, wie auf die
Elemente einer Liste oder einer Menge: Die erste Zahl ist der größte gemein-
same Teiler der beiden Zahlen 27 und 99.
g:= igcdex(a, b)[1]
Die anderen beiden Zahlen entsprechen den Werten k und l von oben.
k:= igcdex(a, b)[2];
l:= igcdex(a, b)[3]
Wir machen die Probe:
g = k * a + l * b
Das Ergebnis ist korrekt. Das nächste Beispiel kann man nicht mehr so leicht
im Kopf nachrechnen:
a:= 32723737821:
b:= 38238938919109350:
g:= igcdex(a, b)[1];
k:= igcdex(a, b)[2];
l:= igcdex(a, b)[3]
Auch hier machen wir wieder die Probe:
g = k * a + l * b
Korrekt!
Nun zur Berechnung des kleinsten gemeinsamen Vielfachen zweier ganzer
Zahlen. Zuständig für diese Aufgabe ist die MuPAD Funktion "ilcm" (integer
least common multiple).
Ihre Verwendung ist ganz analog zu der von "igcd". Die Funktion "ilcm" erhält
stets zwei Argumente: Eine ganze Zahl a und eine ganze Zahl b, d.h. also ein
Aufruf ist immer von der Form "ilcm( a, b )". Als Rückgabewert liefert uns die
Funktion ilcm das kleinste gemeinsame Vielfache von a und b.
Wir berechnen die kleinsten gemeinsamen Vielfachen derjenigen Zahlen, von
denen wir oben schon den größten gemeinsamen Teiler bestimmt haben:
ilcm(10, 3)
ilcm(10, 4)
ilcm(250, 20)
ilcm(236236, 23889389218926)
Entsprechende Funktionen zu denen, die wir bisher für ganze Zahlen kennen-
gelernt haben, gibt es auch für Polynome in MuPAD.
Sie sind unter den Namen "gcd", "gcdex" und "lcm" in der Standardbibliothek
verfügbar. Ihre Verwendung ist ganz analog zu der der entsprechenden
Funktionen für ganze Zahlen, die wir soeben kennengelernt haben. Aus diesem
Grund verzichten wir hier auch auf eine detaillierte Beschreibung und verweisen
auf die entsprechenden Hilfeseiten des MuPAD Systems, die man über
?gcd
erreichen kann. Dort finden sich auch hinreichend viele Beispiele, die den
Umgang mit den Funktionen zusätzlich erläutern.
________________________________________________________________________________
Übungen:
1. Berechnen Sie den größten gemeinsamen Teiler sowie die Zahlen k und l von oben und das
__kleinste gemeinsame Vielfache der folgenden Zahlenpaare:
363, 272
231, 890
324234, 34
234234224, 957295074
_______________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe
wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die
Bücher können unter www.schule.mupad.de/literatur kostenfrei kopiert werden.
_______________________________________________________________________________