Der Eu­kli­di­sche Al­go­rith­mus

Ent­de­cker-Auf­trä­ge:

1. Be­trach­te die Zah­len 56 und 32. Es gilt ggT(32; 56) = 8. Wir zer­le­gen nun beide Aus­gangs­zah­len mit­hil­fe ihres ggT und er­hal­ten 32 = 4 · 8 und 56 = 7 · 8. Mit­hil­fe die­ser Zer­le­gun­gen kann man über die Dif­fe­renz 56 – 32 aus­sa­gen, dass sie 3 · 8 sein muss, ohne sie ex­pli­zit aus­zu­rech­nen.

   a.) Be­grün­de diese Aus­sa­ge.

   b.) Aus die­sem Wis­sen folgt eine wei­te­re Aus­sa­ge: Die Dif­fe­renz 56 – 32 ist eben­falls durch 8 teil­bar, d.h. der ggT von 56 und 32 teilt auch die Dif­fe­renz 56 – 32. Be­grün­de.

   c.) Die­ses Vor­ge­hen funk­tio­niert nicht nur für die Zah­len 56 und 32, son­dern für be­lie­bi­ge Zah­len. Führe es an den Zah­len­paa­ren 25 und 35, 4 und 12 sowie 26 und 65 er­neut durch.

2. Dar­über hin­aus kann man zei­gen, dass der ggT von 56 und 32 nicht nur „ir­gend­ein“ Tei­ler von 56 – 32 ist, son­dern dass er sogar der ggT von 56 – 32 und 32 sein muss.

   a.)* Be­grün­de diese Aus­sa­ge.

   b.) Diese Er­kennt­nis hat der grie­chi­sche Ma­the­ma­ti­ker Eu­klid von Alex­an­dria 325 v. Chr. In sei­nem Werk „Die Ele­men­te“ wei­ter­ge­führt. Er ent­wi­ckel­te dar­aus den so­ge­nann­ten Eu­kli­di­schen Al­go­rith­mus, mit dem man den ggT zwei­er Zah­len be­stim­men kann. Am Bei­spiel der Zah­len 56 und 32 geht der Al­go­rith­mus so:

   ggT(56; 32) = ggT(24; 32) = ggT(24; 8) = ggT(16; 8) = ggT(8; 8) = 8

   Über­le­ge dir, wie Eu­klid von links nach rechts in die­ser „Ket­ten­glei­chung“ vor­geht. Über­prü­fe dein Vor­ge­hen an den Zah­len­paa­ren aus 1c.), indem du deren ggT mit dem glei­chen Vor­ge­hen be­stimmst und mit den ggT-Wer­ten aus dei­nen Lö­sun­gen von 1c.) ab­gleichst. Schrei­be dann eine An­lei­tung, wie man auf diese Weise den ggT zwei­er be­lie­bi­ger Zah­len be­stim­men kann. Es lie­gen Hil­fe­kärt­chen be­reit, falls du nicht wei­ter­kommst.

3. Führe den Eu­kli­di­schen Al­go­rith­mus an den fol­gen­den Zah­len­paa­ren durch.

   a.) 9 und 30

   b.) 226 und 904

   c.) 1215 und 2115

4. * Pro­gram­mie­re den Eu­kli­di­schen Al­go­rith­mus so, dass der An­wen­der zwei Zah­len ein­ge­ben kann und den ggT als Aus­ga­be er­hält.

Hil­fe­kar­ten

...​in der Geo­me­trie

Grup­pe 1

Grup­pe 2

Grup­pe 3

Der Eu­kli­di­sche Al­go­rith­mus: Her­un­ter­la­den [odt][466 KB]

Der Eu­kli­di­sche Al­go­rith­mus: Her­un­ter­la­den [pdf][857 KB]

Wei­ter zu Hil­fe­kar­ten