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
14-2-2021
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 [https://en.wikipedia.org/wiki/Euclidean_algorithm#Proof_of_validity]
kphart
14-2-2021
#91526 - Telproblemen - Student hbo