WisFaq!

Re: Ggd schrijven als lineaire combinatie

Hallo,

Deze snap ik, maar dan zit ik alweer in de knoop met de ggd van 12 en 17.

Dit is wat ik heb:

17 = 12 + 5
12 = 5 · 2 + 2
5 = 2 · 2 + 1 (ggd)
2 = 1 · 2 + 0

1 = 5 - 2 · 2
2 = 12 - 5 · 2

Daaruit volgt dat ik 1 ook zo kan schrijven:
1 = 5 - (12 - 5 · 2) · 2
1 = 5 - 12 · 2 + 5 · 4

Bij die laatste stap ga ik volgens mij in de fout, want volgens de cursus kun je de ggd(17,12) lineair schrijven als zijnde 5 · 17 - 7 · 12 = 1?

Pieter
28-5-2006

Antwoord

Je moet alle drie de eerste stappen uit de berekening van de ggd gebruiken:
Het beste kun je die er gelijk in omgeschreven vorm achter schrijven:
17=1·12+5 $\Rightarrow$ 5=17-1·12
12=2·5+2 $\Rightarrow$ 2=12-2·5
5=2·2+1 $\Rightarrow$ 1=5-2·2

Je begint goed bij de derde stap:
1=5-2·2,
je vult nu 2=12-2·5 uit de tweede stap in:
1=1·5-2·(12-2·5)
Deze vereenvoudig je tot 1=5·5-2·12.
Dan vul je de eerste stap (5=17-1·12 ) in:
1=-2·12+5·(17-1·12)
En deze vereenvoudig je tot:
1=-7·12+5·17

Een Javascript programma dat dit allemaal netjes voor je uitschrijft kun je vinden op inverse van a mod b (vul voor a en b de twee getallen in waarvan je de ggd als lineaire combinatie wilt schrijven. (Overigens werkt deze alleen als de ggd=1)

hk
28-5-2006