Euklids algoritme: Forskelle mellem versioner
Content deleted Content added
Inc (diskussion | bidrag) m →Bevis for korrekthed: erstatter {{math}} med <math> Tag: 2017-kilderedigering |
Inc (diskussion | bidrag) →Bevis for korrekthed: Skriver al matematik med <math> og retter på nogle fejl i oversættelsen fra enwiki. Tag: 2017-kilderedigering |
||
Linje 54:
=== Bevis for korrekthed ===
Gyldigheden af Euklids algoritme kan bevises ved et to-trins argument.<ref>{{Harvnb|Stark|1978|pp=16–20}}</ref> I det første trin vises at endelige resterende
:< For at vise at ''r'' <sub>''N'' −1</sub> går op i både ''a'' og ''b'' (det første trin), ses først at ''R'' <sub>''N'' −1</sub> går op i sin forgænger ''r'' <sub>''N'' −2</sub>▼
▲For at vise at
:<math>r_{N-2}=q_Nr_{N-1}</math>
da den sidste rest
▲da den sidste rest ''r'' <sub>''N''</sub> er nul. ''r'' <sub>''N'' −1</sub> går også op i den næste forgænger ''r'' <sub>''N'' −3</sub>
:<math>r_{N-3}=q_{N-1}r_{N-2}+r_{N-1}</math>
fordi den går op i begge led på højre side af ligningen. Ved at gentage dette argument igen og igen, ses det at
:<math>r_{N-1}\le g</math>
I det andet trin vises det at ethvert naturligt tal ''c'' der går op i både <math>a</math> og <math>b</math> (med andre ord enhver fælles divisor af <math>a</math> og <math>b</math>), også går op i alle resterne <math>r_k</math>. Pr. definition kan <math>a</math> og <math>b</math> skrives som multipla af <math>c</math>:
▲fordi den går op i begge led på højre side af ligningen. Ved at gentage dette argument igen og igen, ses det at ''r'' <sub>''N'' −1</sub> går op i alle de foregående rester, inklusive ''a'' og ''b'' . Ingen af de foregående rester ''r'' <sub>''N'' −2</sub>, ''r'' <sub>''N'' −3</sub> osv. går op i ''a'' og ''b'', da de efterlader en rest. Da ''r'' <sub>''N'' −1</sub> er en fælles divisor af ''a'' og ''b'', må ''r'' <sub>''N'' −1</sub> ≤ ''g'' .
:<math>\begin{align}a&=mc\\ b&=nc\end{align}</math>
hvor <math>m</math> og <math>n</math> er naturlige tal. Derfor går <math>c</math> op i den indledende rest <math>r_0</math>, da
:<math>r_0=a-q_0b=mc-q_0nc=(m-q_0n)c</math>
Et analogt argument viser, at <math>c</math> også går op i de efterfølgende rester <math>r_1</math>, <math>r_2</math> osv. Derfor skal den største fælles divisor <math>g</math> gå op i <math>r_{N-1}</math>, hvilket indebærer, at
:<math>g=sfd(a,b)=gcd(b,r_0)=sdf(r_0,r_1)=...=sfd(r_{N-2},r_{N-1})=r_{N-1}</math>▼
:<math>g\le r_{N-1}</math>
Da den første del af argumentet viste det omvendte (<math>r_{N-1} \le g</math>), følger det, at
:<math>g= r_{N-1}</math>
Således er <math>g</math> den største fælles divisor af alle de efterfølgende par:<ref>{{Harvnb|Knuth|1997|p=320}}</ref>
▲:<math>g=\text{sfd}(a,b)=\text{gcd}(b,r_0)=\text{sdf}(r_0,r_1)=...=\text{sfd}(r_{N-2},r_{N-1})=r_{N-1}</math>
=== Gennemregnet eksempel ===
|