Paderborner Mathezirkel: Der Euklidische Algorithmus

Wenn man den größten gemeinsamen Teiler von 24.375 und 10.935 finden will, so kann man dieses mit Hilfe der Primfaktorzerlegungen der beiden Zahlen machen. Aber bei so großen Zahlen ist das recht mühselig! Eine bequemere und schnellere Vorgehensweise liefert der Euklidische Algorithmus, der mit wiederholter Division mit Rest den größten gemeinsamen Teiler zweier natürlicher Zahlen berechnet. – Nach den Grundlagen zur Teilbarkeit beweisen wir den Satz über die Division mit Rest und führen nach diesen Vorbereitungen den Euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier natürlicher Zahlen ein. Selbstverständlich werden wir den Euklidischen Algorithmus nicht nur für Beispiele anwenden, sondern wir werden auch beweisen, dass dieser immer den größten gemeinsamen Teiler berechnet! – Für Teilnehmer*innen mit Vorkenntnissen gibt es darauf aufbauend noch Zusatzaufgaben, in denen das Lemma von Bézout und das Lemma vo n Euklid bewiesen werden.