De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

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

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



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3