|
|
|
\require{AMSmath}
Reageren...
Re: Kwantoren
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 a2,b2, hence so are a3,b3,… 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]= m2a2+n2b2=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
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).
Gebruik dit formulier alleen om te reageren op de inhoud van de vraag en/of het
antwoord hierboven. Voor het stellen van nieuwe vragen kan je gebruik maken
van een vraag stellen in het menu aan de linker kant. Alvast bedankt!
|
