![\"EuklidGrafikNeuD\"](\"http:\/\/horstth.de\/wp-content\/uploads\/2013\/10\/EuklidGrafikNeuD.jpg\")
<\/a>Schrittzahl beim Euklidischen Algorithmus, siehe Text<\/p><\/div>\n
Nach M. Bauer1<\/sup><\/b>\u00a0 <\/sup>sind die Sch\u00fcler(innen) der sechsten Klasse davon \u00fcberzeugt, dass es dumme Br\u00fcche<\/b> gibt. Dumm sind Br\u00fcche dann, wenn es schwierig ist herauszufinden, ob und wie man sie k\u00fcrzen kann. W\u00e4hrend man bei 25\/75 sofort sieht, dass man mit 25 k\u00fcrzen kann, braucht man etwas l\u00e4nger, um festzustellen, dass in 391\/153 Z\u00e4hler und Nenner durch 17 teilbar sind. Die Zeit, die man ben\u00f6tigt, um den gr\u00f6\u00dften gemeinsamen Teiler (ggT<\/i>)<\/b> von Z\u00e4hler und Nenner zu finden, l\u00e4sst sich quantitativ angeben als Anzahl der Schritte, die der Euklidische Algorithmus<\/b> zu seiner Bestimmung erfordert. Mathematisch interessante Fragen, die sich aus dieser Tatsache ergeben, werden in der Arbeit von Bauer1<\/sup> er\u00f6rtert. Euklidischer Algorithmus: <\/span>Sind x<\/i> und y<\/i> zwei Zahlen, deren ggT<\/i> bestimmt werden soll und f\u00fcr die gilt x <\/i>> y<\/i>, so bilde die Differenz x <\/i>– y. <\/i>Du hast damit eine dritte Zahl gefunden, die den gesuchten Teiler enth\u00e4lt. Statt den ggT<\/i> von x<\/i> und y<\/i> zu suchen, bestimme jetzt den ggT<\/i> der beiden Zahlen y<\/i> und x <\/i>– y<\/i>. Setze dieses Verfahren solange fort, bis eine der Zahlen Null ist. Die von Null verschiedene Zahl des letzten Paares ist der gesuchte ggT.<\/i><\/span><\/span><\/p>\n Der Euklidische Algorithmus ist in der Tat faszinierend \u2013 und die Darstellung der Schrittzahl in einem Koordinatensystem f\u00fchrt zu einer eindrucksvollen Grafik. Hier mein Versuch einer solchen Darstellung: Die Abbildung zeigt die Schrittzahl, die zur Bestimmung des ggT<\/i>(x<\/i>,y<\/i>) nach Euklid ben\u00f6tigt wird, als Funktion von x<\/i> und y<\/i>. Jedes Karo repr\u00e4sentiert ein Zahlenpaar (x<\/i>,y<\/i>) und ist entsprechend der relativen Schrittzahl gef\u00e4rbt. Da der ggT<\/i> symmetrisch in x<\/i> und y<\/i> ist \u2013 es gilt ggT<\/i>(x<\/i>,y<\/i>) = ggT<\/i>(y<\/i>,x<\/i>), wird das Muster der Karos unterhalb der Winkelhalbierenden an dieser nach oben gespiegelt. Karos von Paaren mit maximaler Schrittzahl sind rot gef\u00e4rbt, solche mit der um eins, zwei oder drei gegen\u00fcber der H\u00f6chstzahl verminderten Schrittzahl magenta, cyan bzw. blau. Alle Karos, die Paaren mit noch kleinerer Schrittzahl entsprechen, erscheinen grau \u2013 bis auf diejenigen, die nur einen einzigen Schritt erfordern, sie wurden wei\u00df gef\u00e4rbt. <\/span>Viele Paare maximaler Schrittzahl (rote Karos) liegen in etwa in der N\u00e4he der Geraden x<\/i> = 0,618 y<\/i> bzw. y<\/i> = 0,618 x<\/i> (0,618 ist das Verh\u00e4ltnis der kleineren zur gr\u00f6\u00dferen Strecke beim Goldenen Schnitt<\/b>). Es gibt jedoch Paare deutlich oberhalb dieser Geraden. Auch die magentafarbenen Karos (Schrittzahl um eins kleiner als die maximale Schrittzahl) gruppieren sich in der N\u00e4he von Geraden, zum Beispiel x<\/i> = 3y<\/i>\/8 (bzw. y<\/i> = 3x<\/i>\/8). Die durch die wei\u00dfen Karos angedeuteten Geraden entsprechen den Gleichungen x<\/i> = y<\/i>\/2 (y<\/i> = x<\/i>\/2), x<\/i> = y<\/i>\/3 (y<\/i> = x<\/i>\/3), usw. In diesen F\u00e4llen ist x<\/i> (y<\/i>) die H\u00e4lfte, ein Drittel, usw. von y<\/i> (x<\/i>), so dass der Algorithmus nur einen Schritt ben\u00f6tigt. Mehr zum Euklidischen Algorithmus hier<\/a>.<\/p>\n 1<\/span> <\/sup>Bauer, M.<\/strong>: Die d\u00fcmmsten Br\u00fcche und die bl\u00f6desten Nenner, mathe-plus 2<\/span>, (1), S. 12 (1985)<\/span><\/span><\/p>\n","protected":false},"excerpt":{"rendered":" Nach M. Bauer1\u00a0 sind die Sch\u00fcler(innen) der sechsten Klasse davon \u00fcberzeugt, dass es dumme Br\u00fcche gibt. Dumm sind Br\u00fcche dann, wenn es schwierig ist herauszufinden, ob und wie man sie k\u00fcrzen kann. W\u00e4hrend man bei 25\/75 sofort sieht, dass man mit 25 k\u00fcrzen kann, braucht man etwas l\u00e4nger, um festzustellen, dass in 391\/153 Z\u00e4hler und Nenner durch 17 teilbar sind.…<\/p>\n
\n<\/p>\n