Euklids algoritme: Forskelle mellem versioner

Content deleted Content added
m →‎Bevis for korrekthed: erstatter {{math}} med <math>
Tag: 2017-kilderedigering
→‎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 ''r'' <submath>''r_{N'' −1-1}</submath>, der altså er forskellig fra nul, går op i både ''<math>a''</math> og ''<math>b'' </math>. Da det er en fælles divisor, skal den være mindre end eller lig med den største fælles divisor ''<math>g'' </math>. I det andet trin vises det, at enhver fælles divisor af ''<math>a''</math> og ''<math>b''</math>, inklusiveinklusiv ''<math>g''</math>, skal gå op i ''r'' <submath>''r_{N'' −1-1}</submath>, og derfor skal ''<math>g''</math> være mindre end eller lig med ''R'' <submath>''r_{N'' −1-1}</submath> . Disse to konklusioner betyder sammen, at ''r''
:<submath>''r_{N'' −1-1}=g</submath> &nbsp; = &nbsp; ''g'' .
 
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 ''r'' <submath>''r_{N'' −1-1}</submath> går op i både ''<math>a''</math> og ''<math>b''</math> (det første trin), ses først, at ''R'' <submath>''r_{N'' −1-1}</submath> går op i sin forgænger ''r'' <submath>''r_{N'' −2-2}</submath>
:<math>r_{N-2}=q_Nr_{N-1}</math>
da den sidste rest ''r'' <submath>''N''r_N</submath> er nul. ''r'' <submath>''r_{N'' −1-1}</submath> går også op i den næste forgænger ''r'' <submath>''r_{N'' −3-3}</submath>
 
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 ''r'' <submath>''r_{N'' −1-1}</submath> går op i alle de foregående rester, inklusive ''<math>a''</math> og ''<math>b'' </math>. Ingen af de foregående rester ''r'' <submath>''r_{N'' −2-2}</submath>, ''r'' <submath>''r_{N'' −3-3}</submath> osv. går op i ''<math>a''</math> og ''<math>b''</math>, da de efterlader en rest. Da ''r'' <submath>''r_{N'' −1-1}</submath> er en fælles divisor af ''<math>a''</math> og ''b'', må ''r'' <submath>''N'' −1b</submath>, &nbsp; ≤ &nbsp; ''g'' .
:<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> &nbsp; ≤ &nbsp; ''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
I det andet trin vises det at ethvert naturligt tal ''c'' der går op i både ''a'' og ''b'' (med andre ord enhver fælles divisor af ''a'' og ''b''), også går op i alle resterne ''r''<sub>''k''</sub>. Per definition kan ''a'' og ''b'' skrives som multipla af ''c'': ''a'' &nbsp; = &nbsp; ''mc'' og ''b'' &nbsp; = &nbsp; ''nc'', hvor ''m'' og ''n'' er naturlige tal. Derfor går ''c'' op i den indledende rest ''r''<sub>0,</sub> da ''r''<sub>0</sub> = &nbsp; ''-en'' &nbsp; - &nbsp; ''q'' <sub>0</sub> ''b'' &nbsp; = &nbsp; ''mc'' &nbsp; - &nbsp; ''q'' <sub>0</sub> ''nc'' &nbsp; = &nbsp; ( ''m'' &nbsp; - &nbsp; ''q'' <sub>0</sub> ''n'' ) ''c'' . Et analogt argument viser at ''c'' også går op i de efterfølgende rester ''r'' <sub>1</sub>, ''r'' <sub>2</sub> osv. Derfor skal den største fælles divisor ''g'' gå op i ''r'' <sub>''N'' −1</sub>, hvilket indebærer, at ''g'' &nbsp; ≤ &nbsp; ''r'' <sub>''N'' −1</sub> . Da den første del af argumentet viste det omvendte ( ''r'' <sub>''N'' −1</sub> &nbsp; ≤ &nbsp; ''g'' ) følger det, at ''g'' &nbsp; = &nbsp; ''r'' <sub>''N'' −1</sub> . Således er ''g'' den største fælles divisor af alle de efterfølgende par: <ref>{{Harvnb|Knuth|1997|p=320}}</ref>
:<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>
: {{Math|1=''g'' = sfd(''a'', ''b'') = gcd(''b'', ''r''<sub>0</sub>) = sfd(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = sfd(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''r''<sub>''N''−1</sub>.}}
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 ===