\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fswiss\fprq2 Helvetica;}{\f4\fswiss\fprq2 Arial;}{\f5\froman\fprq2 Times New Roman;}{\f6\fmodern\fprq1 Courier New;}}
{\colortbl\red0\green0\blue0;\red0\green0\blue255;\red0\green128\blue0;\red255\green0\blue0;\red255\green255\blue255;\red0\green0\blue128;}
\deflang1031\pard\ri4\plain\f6\fs20\cf0\b ________________________________________________________________________________
\par
\par \plain\f6\fs20\cf0 Inhalt....: Berechnung des ggT und kgV
\par Kategorie.: Grundkurs
\par Mathematik: Zahlentheorie, Kryptographie
\par MuPAD.....: 3.0.0
\par Datum.....: 2004-03-31
\par Autoren...: Kai Gehrs
\par Funktionen: igcd, igcdex, ilcm
\par \plain\f6\fs20\cf0\b ________________________________________________________________________________
\par \plain\f4\fs36\cf0\b
\par \plain\f4\fs40\cf0\b Berechnung des ggT und kgV
\par
\par \plain\f4\fs24\cf2 Dieses Arbeitsblatt ist Bestandteil des \plain\f4\fs24\cf2\b MuPAD Grundkurses\plain\f4\fs24\cf2 .\plain\f5\fs24
\par
\par \plain\f4\fs28 Zu den elementarsten Algorithmen der Zahlentheorie und der Kryptographie
\par geh\'f6ren die Berechnung des gr\'f6\'dften gemeinsamen Teilers durch den
\par Euklidischen Algorithmus. Hier sehen wir, wie man mit MuPAD den gr\'f6\'dften
\par gemeinsamen Teiler und das kleinste gemeinsame Vielfache von ganzen
\par Zahlen (und, ganz kurz am Rande, von Polynomen) berechnen kann.
\par
\par Zur Berechnung des gr\'f6\'dften gemeinsamen Teilers (ggT) zweier ganzer
\par Zahlen steht in MuPAD die Funktion "igcd" (integer greatest common divisor)
\par bereit.
\par
\par Die Funktion igcd erh\'e4lt stets zwei Argumente: Eine ganze Zahl a und eine
\par ganze Zahl b, d.h. also ein Aufruf ist immer von der Form "igcd( a, b )". Als
\par R\'fcckgabewert liefert uns die Funktion igcd den gr\'f6\'dften gemeinsamen Teiler
\par von a und b.
\par
\par Einige kleine Beispiele verdeutlichen wie immer den Umgang mit dieser
\par neuen Funktion:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}igcd(10, 3)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}igcd(10, 4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}igcd(250, 20)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}igcd(236236, 23889389218926)
\par \pard\ri4\plain\f4\fs28 Erinnern wir uns an den Euklidischen Algorithmus zur Berechnung des gr\'f6\'dften
\par gemeinsamen Teilers, so liefert dieser auch ganze Zahlen k und l, so dass ggT
\par ( a, b ) = k * a + l * b gilt. Um den gr\'f6\'dften gemeinsamen Teiler und zus\'e4tzlich
\par die Zahlen k und l zu berechnen, kann die Funktion "igcdex" benutzt werden.
\par
\par Die Funktion "igcdex" erh\'e4lt stets zwei Argumente: Eine ganze Zahl a und eine
\par ganze Zahl b, d.h. also ein Aufruf ist immer von der Form "igcdex( a, b )". Als
\par R\'fcckgabewert liefert uns die Funktion igcdex eine Sequenz von drei ganzen
\par Zahlen g, k, l. Dabei ist g der gr\'f6\'dfte gemeinsame Teiler von a und b und k
\par und l erf\'fcllen die oben beschriebene Gleichung, d.h. g = k * a + l * b. Auch hier
\par wieder einige Beispiele:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}a:= 27: b:= 99:
\par {\pntext\f1\'b7\tab}igcdex(a, b)
\par \pard\ri4\plain\f4\fs28 Auf die einzelnen Zahlen der Sequenz greift man genauso zu, wie auf die
\par Elemente einer Liste oder einer Menge: Die erste Zahl ist der gr\'f6\'dfte gemein-
\par same Teiler der beiden Zahlen 27 und 99.
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}g:= igcdex(a, b)[1]
\par \pard\ri4\plain\f4\fs28 Die anderen beiden Zahlen entsprechen den Werten k und l von oben.
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}k:= igcdex(a, b)[2];
\par \pard\li600\ri1\fi-300\plain\f6\fs28\cf3 l:= igcdex(a, b)[3]
\par \pard\ri4\plain\f4\fs28 Wir machen die Probe:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}g = k * a + l * b
\par \pard\ri4\plain\f4\fs28 Das Ergebnis ist korrekt. Das n\'e4chste Beispiel kann man nicht mehr so leicht
\par im Kopf nachrechnen:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}a:= 32723737821:
\par \pard\li600\ri1\fi-300\plain\f6\fs28\cf3 b:= 38238938919109350:
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}g:= igcdex(a, b)[1];
\par \pard\li600\ri1\fi-300\plain\f6\fs28\cf3 k:= igcdex(a, b)[2];
\par l:= igcdex(a, b)[3]
\par \pard\ri4\plain\f4\fs28 Auch hier machen wir wieder die Probe:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}g = k * a + l * b
\par \pard\ri4\plain\f4\fs28 Korrekt!
\par
\par Nun zur Berechnung des kleinsten gemeinsamen Vielfachen zweier ganzer
\par Zahlen. Zust\'e4ndig f\'fcr diese Aufgabe ist die MuPAD Funktion "ilcm" (integer
\par least common multiple).
\par
\par Ihre Verwendung ist ganz analog zu der von "igcd". Die Funktion "ilcm" erh\'e4lt
\par stets zwei Argumente: Eine ganze Zahl a und eine ganze Zahl b, d.h. also ein
\par Aufruf ist immer von der Form "ilcm( a, b )". Als R\'fcckgabewert liefert uns die
\par Funktion ilcm das kleinste gemeinsame Vielfache von a und b.
\par
\par Wir berechnen die kleinsten gemeinsamen Vielfachen derjenigen Zahlen, von
\par denen wir oben schon den gr\'f6\'dften gemeinsamen Teiler bestimmt haben:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}ilcm(10, 3)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}ilcm(10, 4)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}ilcm(250, 20)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}ilcm(236236, 23889389218926)
\par \pard\ri4\plain\f4\fs28 Entsprechende Funktionen zu denen, die wir bisher f\'fcr ganze Zahlen kennen-
\par gelernt haben, gibt es auch f\'fcr Polynome in MuPAD.
\par
\par Sie sind unter den Namen "gcd", "gcdex" und "lcm" in der Standardbibliothek
\par verf\'fcgbar. Ihre Verwendung ist ganz analog zu der der entsprechenden
\par Funktionen f\'fcr ganze Zahlen, die wir soeben kennengelernt haben. Aus diesem
\par Grund verzichten wir hier auch auf eine detaillierte Beschreibung und verweisen
\par auf die entsprechenden Hilfeseiten des MuPAD Systems, die man \'fcber
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f6\fs28\cf3 {\pntext\f1\'b7\tab}?gcd
\par \pard\ri4\plain\f4\fs28
\par erreichen kann. Dort finden sich auch hinreichend viele Beispiele, die den
\par Umgang mit den Funktionen zus\'e4tzlich erl\'e4utern.
\par
\par \plain\f6\fs20\cf0\b ________________________________________________________________________________
\par \plain\f4\fs22\cf1\b
\par \plain\f4\fs22\cf5\b \'dcbungen:
\par 1.\plain\f4\fs22\cf5 Berechnen Sie den gr\'f6\'dften gemeinsamen Teiler sowie die Zahlen k und l von oben und das
\par \plain\f4\fs22\cf4 __\plain\f4\fs22\cf5 kleinste gemeinsame Vielfache der folgenden Zahlenpaare:
\par
\par \pard\li500\ri4\plain\f4\fs22\cf5 363, 272
\par 231, 890
\par 324234, 34
\par 234234224, 957295074
\par \pard\ri4\plain\f6\fs20\cf0\b _______________________________________________________________________________
\par \plain\f4\fs22\cf0
\par \plain\f4\fs22\cf2\b Anmerkungen:\plain\f4\fs22\cf2
\par \plain\f4\fs20\cf2\b 1\plain\f4\fs20\cf2 . Weitere Anregungen finden Sie in der Buchreihe \plain\f4\fs20\cf3 Mathematik 1 x anders\plain\f4\fs20\cf2 . In dieser Reihe
\par wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die
\par B\'fccher k\'f6nnen unter \plain\f3\fs20\cf1 www.schule.mupad.de/literatur\plain\f4\fs20\cf2 kostenfrei kopiert werden.
\par \plain\f4\fs20\cf1
\par \plain\f6\fs20\cf0\b _______________________________________________________________________________
\par \plain\f6\fs28\cf3
\par
\par }