Mathematik HTL 1, Schulbuch

34 Zahlen Dieses Verfahren zur Berechnung des ggT von zwei positiven natürlichen Zahlen heißt euklidischer Algorithmus und war schon vor mehr als 2000 Jahren bekannt. Wir fassen unsere Überlegungen als Rechenverfahren zusammen:  Gegeben sind zwei positive natürliche Zahlen a und b. Solange a und b verschieden sind, ersetze die größere dieser zwei Zahlen durch die Differenz  der größeren und der kleineren. Sobald a und b gleich sind, ist das Verfahren beendet und diese Zahl ist der gesuchte ggT.  140 Kürze 123 _ 45 bestmöglich, indem du dazu den ggT(123,45) berechnest. Da 123 ≠ 45 ist, berechnen wir 123 – 45 = 78 und können statt ggT(123,45) einfach ggT(78,45) berechnen. Da 78 ≠ 45 ist, berechnen wir 78 – 45 = 33 und können statt ggT(78,45) einfach ggT(45,33) berechnen. So fahren wir fort und erhalten: ggT(123,45) = ggT(78,45) = ggT(45,33) = ggT(33,12) = ggT(21,12) = ggT(12,9) = = ggT(9,3) = ggT(6,3) = ggT(3,3) = 3 Wer „sieht“, dass ggT(9,3) = 3 ist (weil ja 3 ein Teiler von 9 ist), kann natürlich mit ggT(9,3) = 3 aufhören. Es ist also 123 _ 45 = 3·41 _ 3·15 = 41 _ 15 . Wenn eine der zwei Zahlen „viel größer“ als die andere ist, muss man von der größeren mehrfach die kleinere abziehen. 141 Berechne ggT(123,9). ggT(123,9) = ggT(114,9) = ggT(105,9) = ggT(96,9) = ggT(87,9) = ggT(78,9) = ggT(69,9) = = ggT(60,9) = ggT(51,9) = ggT (42,9) = ggT(33,9) = ggT(24,9) = ggT(15,9) = = ggT(9,6) = ggT(9,3) = ggT(6,3) = ggT(3,3) = 3 Dies ist recht langwierig! Die mehrfache Subtraktion können wir aber abkürzen. Wir erinnern uns an Abschnitt 1.1: Mehrfache Subtraktion ist nichts anderes als Division mit Rest! Tipp Wenn wir mehrfache Subtraktion derselben Zahl jeweils zu einer Division mit Rest zusammen- fassen, können wir den Euklidischen Algorithmus auch so formulieren: Gegeben sind zwei positive natürliche Zahlen.  Solange die größere der beiden Zahlen nicht ein Vielfaches der kleineren ist  (und daher der Rest von der größeren Zahl nach Division mit Rest durch die kleinere nicht 0 ist), ersetze die größere dieser zwei Zahlen durch ihren Rest nach Division mit Rest durch die kleinere. Sobald die größere Zahl ein Vielfaches der kleineren ist, also der Rest der größeren nach  Division durch die kleinere gleich 0 ist, ist das Verfahren beendet und die kleinere Zahl ist der gesuchte ggT. 142 Berechne ggT(123,9) durch Division mit Rest. 123 = 13·9 + 6, d.h. ggT(123,9) = ggT(9,6) 9 = 1·6 + 3, d.h. ggT(9,6) = ggT(6,3) Nachdem 6 ein Vielfaches von 3 ist, ist 3 = ggT(6,3) = ggT(9,6) = ggT(123,9). In abgekürzter Schreibweise: ggT(123,9) = ggT(9,6) = ggT(6,3) = 3 euklidischer Algorithmus B ggT mit dem euklidischen Algorithmus berechnen B ggT mit dem euklidischen Algorithmus berechnen B ggT mit dem euklidischen Algorithmus berechnen (mit Division mit Rest) ggb/xls/mcd/tns 2jj3nq xls/mcd/tns fg7j9t ggb/xls q6p77c Nur zu Prüfzwecken – Eigentum des Verlags öbv