WisFaq!

Het algoritme van Euclides

Ik ben laatst begonnen met het boek:
“The history of Mathematics” by John Stilwell pg 41-42
[] staat voor subscript of de 1-ste, 2-de, …i-de stap

Hier word het algoritme als volgt recursief beschreven:
a[1] = max(a,b) – min(a,b)
b[1] =min(a,b),

enz

Nu geld dat de gcd(a,b)= wanneer a[i+1]=b[i+1]

Ik loop echter een beetje vast op het volgende gedeelte:
“If gcd(a,b)=1, then there are integers m,n such that na + mb = 1

The equations:

a[1] = max(a,b) – min(a,b)
b[1] =min(a,b),

a[i+1]=max(a[i],b[i]) – min(a[i],b[i])
b[i+1]=min(a[i],b[i]),

show succesively that a[1],b[1] are integral linear combinations, ma+ nb, of a and b, hence so are a²,b², hence so are a³,b³,… and finally this is true of a[i+1] = b[i+1]. But a[i+1]=b[i+1]=1; hence 1= ma=nb for some integers m,n.”

Over dit stukje heb ik de volgende vragen:
1. Bedoelen ze met “a[1],b[1] are integral linear combinations, ma+ nb, of a and b…” dat
a. ma+nb=m[1]a[1]+n[1]b[1]= m²a²+n²b²=enz=gcd(a,b) of
b. a[1] = m[a1]a+n[a1]b
b[1] = n[b1]+n[b1]b
2. En verder stel dat de gcd(a,b)=1, is er dan maar 1 set integers m,n waarvoor geldt dat
ma+nb=1 (a en b zijn per defintie al integers)? Met andere woorden ik neem aan dat het als het ware bijectief is wat eigenlijk wel logisch is gezien het feit dat het een lineare fuctie is. Toch lijkt het als je het op deze manier presenteerd, alsof er meerdere integer waarden van m en n zouden kunnen zijn.

Misschien dat iemand me wat meer duidelijkheid/hint zou kunnen geven.

Oke beetje lang verhaal maar hopelijk is het duidelijk. Alvast bedankt .

Gr

Wytze Hoekstra
31-5-2005

Antwoord

Wat helpt in zo'n geval is eens een expliciet voorbeeld door te werken.
Bijvoorbeeld ggd(11,3): a1=11, b1=3; a2=8, b2=3; a3=5, b3=3; a4=2, b4=3; a5=1, b5=2; a6=1, b6=1. Op stap 6 zien we dus dat de ggd gelijk is aan 1.
Een `integral linear combination' van a en b is een uitdrukking van de vorm ma+nb, waarbij m en n gehele getallen zijn. In bovenstaand voorbeeld: a1=1*11+0*3 en b1=0*11+1*3; a2=1*11-1*3 en b2=0*11+1*3; ...; a4=1*11-3*3 en b4=0*11+1*3; a5=b4-a4=-1*11+4*1. Conclusie: 1=-1*11+4*3.
Zo'n schrijfwijze is niet uniek: tel er maar 3*11 bij op en trek er 11*3 van af: 1=2*11-7*3. Zo kun je nog wel meer paren m en n vinden met 1=n*11+m*3 (zelfs oneindig veel).

kphart
31-5-2005