\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:

1. het stopt (dat volgt omdat je een strikt dalende rij natuurlijke getallen maakt)
2. 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$
3. elke gemeenschappelijke deler van $a$ en $b$ deelt alle resten, en dus ook het resultaat.

Zie Proof of validity

kphart
zondag 14 februari 2021

©2001-2024 WisFaq