________________________________________________________________________________
Inhalt....: ggT und kgV
Kategorie.: Handwerkskasten
Mathematik: Zahlentheorie, Kryptographie
MuPAD.....: 3.0.0
Datum.....: 2002-08-14
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: gcd, gcdex, lcm, igcd, igcdex, ilcm
________________________________________________________________________________
Elementare MuPAD-Funktionen:
Größter gemeinsamer Teiler und kleinstes
gemeinsames Vielfaches
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:
1. Argument: Eine ganze Zahl a
2. Argument: 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:
1. Argument: Eine ganze Zahl a
2. Argument: 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 gemeinsame 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:
1. Argument: Eine ganze Zahl a
2. Argument: 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 gemeinsame 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
kennengelernt 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 anlog zu der der entsprechenden Funktionen
für ganze Zahlen, die wir soeben kennengelernt haben. Aus diesem Grund
verzichten wir hier auch auf eine detailierte Beschreibung und verweisen auf
die entsprechenden Hilfeseiten des MuPAD Systems, die man über
?gcd
?gcdex
?lcm
erreichen kann. Dort finden sich auch hinreichend viele Beispiele, die den
Umgang mit den Funktionen zusätzlich erläutern.
________________________________________________________________________________
Aufgaben:
1. Berechnen Sie den gößten gemeinsamen Teiler sowie die Zahlen k und l von oben und das kleinste
gemeinsame Vielfache der folgenden Zahlenpaare:
(a) 363, 272
(b) 231, 890
(c) 324234, 34
(d) 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.
_______________________________________________________________________________