Re: Ggd schrijven als lineaire combinatie

Dit is een reactie op vraag 45593

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
Student Hoger Onderwijs België - zondag 28 mei 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)

zondag 28 mei 2006

©2001-2024 WisFaq