WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Het algoritme van Euclides

Hoe kan ik de correctheid van het algoritme van Euclides beargumenteren, vooral de invoer dat a $>$ b $>$ 0 is (voorwaarden voldoet) en de uitvoer g = ggd (a , b) idd de grootste gemeenschappelijke deler is.

Alvast bedankt!
Bra
Student hbo - zondag 14 februari 2021

Antwoord

Je moet drie dingen bewijzen:
het stopt (dat volgt omdat je een strikt dalende rij natuurlijke getallen maakt)
het resultaat, $d$, deelt $a$ en $b$, dat doe je door terug te lopen door de rij resten: $d$ deelt ze allemaal, en dus ook $a$ en $b$
elke gemeenschappelijke deler van $a$ en $b$ deelt alle resten, en dus ook het resultaat.

Zie Proof of validity

kphart

Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 14 februari 2021