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