Der euklidische Algorithmus - verständlich erklärt
Dan Gö
https://www.youtube.com/watch?v=TUiUqND4Uno

Transkript (automatisch erstellt)

0:03 [Musik] in diesem video schauen wir uns den eugenischen algorithmus genauer an
0:13 er hilft uns dabei den größten gemeinsamen tyler zweier zahlen zu ermitteln anschaulich werden wir dazu eine lineare
0:22 darstellung von thailand verwenden wir suchen also jetzt den größten gemeinsamen tyler zweier zahlen in diesem beispiel von 441 und 546 dazu
0:34 stellen wir diese zahlen zunächst auf einem zahlen strahl da es ist deutlich zu erkennen dass die eine zahl kleiner ist als die andere
0:42 man kann also die größere zahl ausdrücken als die kleinere plus ein rest 546 ist also gleich einmal 441 plus 105 beide streckenlängen 441 und 546
0:58 müssen mit sprüngen der länge des größten gemeinsamen tylers aus messbar sein ansonsten wäre es kein gemeinsamer tyler
1:05 wenn beide aus messbar sind so landet man mit sprüngen der länge des größten gemeinsamen tylers bei 441 und bei 546 das bedeutet aber auch dass der größte
1:19 gemeinsame tyler auch den rest zwischen 441 und 546 also 105 aus messen muss im zweiten schritt des algorithmus wird daher geprüft ob 105 der größte
1:32 gemeinsame teiler von 441 und 546 ist wenn 105 der größte gemeinsame tyler wäre so müsste 105 die strecke 441 restlos ausmessen das tut 105 aber eben
1:47 nicht insgesamt passen vier sprünge der länge 105 in 441 und es bleibt eine reststrecke von 21
1:56 jetzt beginnt unsere argumentation von vorne der größte gemeinsame teiler von 441 und 546 muss auch 105 teilen wir haben 105 probiert und gemerkt dass 105
2:09 nicht 441 teilt es bleibt ein rest von 21 daher muss der größte gemeinsame teiler von 441 und 546 nicht nur 105 sondern auch 21 teil
2:23 wir probieren also erstmal ob 21 der gesuchte größte gemeinsame tyler ist wenn 21 die 105 teilt teilt sie auch 441 und 546
2:36 wir messen die streckenlänge 105 also mit sprüngen der länge 21 aus und sehen dass wir mit fünf sprüngen der länge 21 die streckenlänge 105 restlos aus messen
2:49 es entsteht also diesmal keine reststrecke die sprünge der länge 21 sind somit das größte maß also die längsten sprünge die 441 und 546 restlos
3:02 aus messen in einer gleichung sieht dieser zusammenhang folgendermaßen aus die streckenlänge 105 entspricht 5 x 21 er
3:12 sprünge plus einer recht strecke von 0 in den gleichungen ist der größte gemeinsame tyler bei dem letzten von neun verschiedenen rest abzulesen