Teilermengen<\/h2>\n
Bei kleinen Zahlen ist die Verwendung von Teilermengen f\u00fcr die Berechnung des ggTs sinnvoll, weshalb dieses Verfahren gerne auf der Primarstufe verwendet wird. Um beispielsweise den ggT(18,24) zu berechnen, schreibt man die Teilermengen von 18 und 24 auf:<\/p>\n
T18<\/sub> = {1, 2, 3, 6<\/strong>, 9, 18}<\/p>\n T24<\/sub> = {1, 2, 3, 4, 6<\/strong>, 8, 12, 24)<\/p>\n Es gilt also: ggT(18, 24) = 6.<\/p>\n Da die Menge der Teiler bei grossen Zahlen schnell \u00fcbersichtlich werden kann, ist es h\u00e4ufig einfacher, die Zerlegung in Primfaktoren anzuwenden. Dieses Verfahren wird auf der Sekundarstufe I bevorzugt, weil Primfaktoren in der Zahlentheorie h\u00e4ufig auch behandelt werden. F\u00fcr unser einfaches Beispiel sieht dies so aus:<\/p>\n 18 = 2<\/span><\/strong> \u2219 3<\/span><\/strong> \u2219 3<\/p>\n 24 = 2<\/span><\/strong> \u2219 2 \u2219 2 \u2219 3<\/span><\/strong><\/p>\n Die paarweise eingef\u00e4rbten Primfaktoren k\u00f6nnen nun als Faktoren zur Bildung des ggTs verwendet werden: 2<\/span> \u2219 3<\/span> = 6.<\/p>\n Dieses Verfahren ist zwar mathematisch der Methode mit den Teilermengen vorzuziehen, aber f\u00fcr die Sch\u00fclerinnen und Sch\u00fcler weniger offensichtlich, weshalb es sich hier lohnt, eine Visualisierung zu Hilfe zu nehmen.<\/p>\n Das f\u00fcr die Visualisierung verwendete GeoGebra-Applet, ist unter diesem Link verf\u00fcgbar: https:\/\/www.geogebra.org\/m\/dhVMBqr3<\/a>. Da die einzelnen Primfaktoren der beiden gegebenen Zahlen als unterschiedlich eingef\u00e4rbte Elemente (blau und rot) eines Punkteplots dargestellt werden, wird deren Schnittmenge (violett) sofort ersichtlich. Als Zusatzgewinn ist auch gleich das kleinste gemeinsame Vielfache (kgV) ersichtlich.<\/p>\n Auch wenn die Primfaktorzerlegung schneller zum Ziel f\u00fchrt als die Bestimmung der Teilermengen, kann sich doch f\u00fcr grosse Zahlen sehr schnell sehr aufw\u00e4ndig werden.<\/p>\n Beim euklidischen Algorithmus werden in der einfacheren Form Differenzen, in der etwas schneller zum Ziel f\u00fchrenden Form Quotienten und Reste verwendet. So ergeben sich z.B. f\u00fcr die Zahlen 18 und 24 folgende Schritte:<\/p>\n Auch hier ist es f\u00fcr Sch\u00fclerinnen und Sch\u00fcler nicht einfach nachzuvollziehen, wie genau und weshalb der Algorithmus funktioniert, weshalb sich wieder ein R\u00fcckgriff auf eine Visualisierung empfiehlt. Eine solche hat z.B. die japanische Keio Universit\u00e4t zu Verf\u00fcgung gestellt: Link zur Webseite<\/a>.<\/p>\n Die oben gezeigten Visualisierungen laden zu weiteren mathematischen Untersuchungen ein. Im Hinblick auf den euklidischen Algorithmus ist etwa die Fragen nach Zahlenpaaren interessant, welche m\u00f6glichst viele Schritte bis zur L\u00f6sung ben\u00f6tigen. Dazu muss nat\u00fcrlich der Zahlenraum eingeschr\u00e4nkt werden. Aber einige Versuche zeigen schnell, dass nicht unbedingt die gr\u00f6ssten Zahlen auch die meisten Rechenschritte erfordern, und bereits im Zahlenraum 1000 ergeben sich so viele m\u00f6gliche Kombinationen, dass diese nicht mehr von Hand untersucht werden k\u00f6nnen.<\/p>\n Deshalb lohnt es sich, den Sachverhalt mit dem Computer berechnen zu lassen. Dies kann beispielsweise mit Snap! geschehen, wobei erst einmal eine f\u00fcr den Computer verst\u00e4ndliche Umsetzung des euklidischen Algorithmus geschrieben werden muss. Eine elegante Umsetzung findet sich z.B. in Donald E. Knuths „The Art of Computer Programming. Volume 1: Fundamental Algorithms“ auf Seite 2.<\/p>\n In Snap! kann dieser Algorithmus mit einer Rekursion umgesetzt werden:<\/p>\n Mit Hilfe der geschriebenen Funktion kann nun der ggT f\u00fcr viele Zahlenpaare berechnet werden. F\u00e4rbst man zus\u00e4tzlich Koordinaten (Quadrate) gem\u00e4ss ihrer Iterationstiefe (Anzahl notwendige Schritte zur Berechnung), erh\u00e4lt man sehr schnell einen \u00dcberblick, welche Zahlenpaare interessant sind.<\/p>\n In der oben abgebildeten Grafik entsprechen die roten Punkte beispielsweise den Koordinaten (13, 21) und (34, 21).<\/p>\n Verschafft man sich einen \u00dcberblick \u00fcber eine gr\u00f6ssere Zahlenmenge, erh\u00e4lt man beispielsweise die Koordinaten (34, 55) und (89, 55) als interessante Werte.<\/p>\n Die Visualisierung hilft uns also dabei, interessante Zahlenpaare zu finden. Um die Frage nach dem Zahlenpaar mit den meisten Berechnungsschritten im Zahlenraum bis 1000 zu kl\u00e4ren, reicht dies jedoch noch nicht aus. Hier lohnt es sich, noch einmal zur Visualisierung des ggTs durch die japanische Keio Universit\u00e4t zur\u00fcckzukehren, wobei wir diesmal das Zahlenpaar (34, 55) verwenden:<\/p>\n Es lohnt sich, die Gr\u00f6sse der verwendeten Quadrate zu betrachten: 1, 1, 2, 3, 5, 8, 13, 21, 34, … Sp\u00e4testens an dieser Stelle entdecken einige Sch\u00fclerinnen und Sch\u00fcler der Sekundarstufe 1 die zugrunde liegende Gesetzm\u00e4ssigkeit. Jede Zahl ist jeweils die Summe ihrer beiden Vorg\u00e4ngerzahlen, besser bekannt als Fibonacci-Folge. Indem wir diese fortsetzen, finden wir die entsprechende L\u00f6sung: … 55, 89, 144, 233, 377, 610<\/strong>, 987<\/strong>.<\/p>\n Die Verwendung von computergest\u00fctzten Visualisierungen erleichtert es den Sch\u00fclerinnen und Sch\u00fcler also nicht nur, mathematische Verfahren besser zu verstehen, sie l\u00e4dt auch dazu ein, selbst\u00e4ndig oder im Dialog weitere mathematische Zusammenh\u00e4nge zu entdecken. Ohne Unterst\u00fctzung ist dies zwar auch m\u00f6glich, eine solche Umsetzung w\u00fcrde aber zu viel Zeit in Anspruch nehmen und w\u00e4re weniger offensichtlich.<\/p>\n Das verwendete Snap!-Programm wird durch verschiedene Parameter gesteuert, diese werden im Programm selbst genauer beschrieben.<\/p>\n Link zum Programm: https:\/\/snap.berkeley.edu\/project?user=mattgig&project=ggT<\/a><\/p>\n Knuth (1997, 3rd Edition). The Art of Computer Programming. Volume 1: Fundamental Algorithms. Link: https:\/\/archive.org\/details\/B-001-001-249<\/a><\/p>\n \u00dcbung Euklidischer Algorithmus: https:\/\/www.gigers.com\/matthias\/schule\/euklid_einfach.html<\/a><\/p>\n Visualisierung Euclidean Algorithm: https:\/\/gc.sfc.keio.ac.jp\/fl_img\/course04\/ex\/euclidean_animation\/euclidean.html<\/a><\/p>\n Visualisierung ggT und kgV (GeoGebra): https:\/\/www.geogebra.org\/m\/dhVMBqr3<\/a><\/p>\n Wikipedia: Fibonacci-Folge, https:\/\/de.wikipedia.org\/wiki\/Fibonacci-Folge<\/a><\/p>\nPrimfaktorzerlegung<\/h2>\n
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggt.png\")
Euklidischer Algorithmus<\/h2>\n
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggT_euklid.png\")
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggt_euklid_visuell.png\")
M\u00f6glichkeiten der computergest\u00fctzten Mathematik<\/h2>\n
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggt_euklid_knuth-1024x289.png\")
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggt_snap_function.png\")
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggt_snap_stage.png\")
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggt_snap_stage_fein.png\")
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2019\/11\/ggt_34_55.png\")
Quellen<\/h3>\n