-
Notifications
You must be signed in to change notification settings - Fork 29
Expand file tree
/
Copy pathtest-page.html
More file actions
89 lines (80 loc) · 88.3 KB
/
test-page.html
File metadata and controls
89 lines (80 loc) · 88.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
<!-- Refer to the DOM Spec: https://www.mediawiki.org/wiki/Specs/HTML/2.8.0 -->
<div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr" data-mw-parsoid-version="0.20.0.0-alpha2" id="mwpg">
<section data-mw-section-id="0">
</section>
<section data-mw-section-id="1">
<h2 id="foo=bar">foo=bar</h2>
</section>
<section data-mw-section-id="2">
<h2 id="Link Testing">Link Testing</h3>
<!-- Wiki Links -->
<section data-mw-section-id="3">
<h4 id="Wikilinks">Wiki Links</h4>
<p>
<a rel="mw:WikiLink" href="./Main_Page">alternate linked content</a><br>
</p>
<p>
<a rel="mw:WikiLink" href="./Main_Page">Main Page</a>
</p>
<p>
<a rel="mw:WikiLink" href="./Potato">Potatoes</a>
</p>
<p>
<a href="./Non_existing_page?action=edit&redlink=1" title="Non existing page" rel="mw:WikiLink" class="new" typeof="mw:LocalizedAttrs" data-mw-i18n='{"title":{"lang":"x-page","key":"red-link-title","params":["Non existing page"]}}'>Non existing page</a>
</p>
</section>
<!-- Media Links -->
<section data-mw-section-id="4">
<h4 id="Medialinks">Media Links</h4>
<p>
<a rel="mw:MediaLink" href="//upload.wikimedia.org/wikipedia/commons/0/06/Foo.jpg" title="Foo.jpg">Media:Foo.jpg</a>
</p>
<p>
<a rel="mw:MediaLink" href="//upload.wikimedia.org/wikipedia/commons/0/06/Foo.jpg" title="Foo.jpg">Link text</a>
</p>
</section>
<!-- External Links -->
<section data-mw-section-id="5">
<h4 id="external-links">External Links</h4>
<p>
<a rel="mw:ExtLink" class="external free" href="http://example.com">http://example.com</a>
</p>
<p>
<a rel="mw:ExtLink" class="external text" href="http://example.com">Link content</a>
</p>
</section>
<!-- Magic Links -->
<section data-mw-section-id="6">
<h4 id="magic-links">Magic Links</h4>
<p>
<a rel="mw:WikiLink"
href="./Special:BookSources/9781413304541">
ISBN 978-1413304541
</a>
</p>
<p>
<a rel="mw:ExtLink"
href="http://tools.ietf.org/html/rfc1945">
RFC 1945
</a>
</p>
<a rel="mw:ExtLink"
href="//www.ncbi.nlm.nih.gov/pubmed/20610307?dopt=Abstract">
PMID 20610307
</a>
</p>
</section>
</section>
<section data-mw-section-id="7">
<h2 id="html-entities">HTML entities</h2>
<span typeof="mw:Entity"> </span>
</section>
<section data-mw-section-id="8">
<h2 id="display-space">Display space</h2>
<span typeof="mw:DisplaySpace"> </span>
</section>
<section data-mw-section-id="9">
<h2 id="unsupported-elements">Unsupported Elements</h2>
<div class="mw-heading mw-heading3" id="mwI_g"><h3 id="Procedure">Procedure</h3><span class="mw-editsection" id="mwI_k"><span class="mw-editsection-bracket" id="mwI_o">[</span><a href="/w/index.php?title=Euclidean_algorithm&action=edit&section=3" title="Edit section: Procedure" id="mwI_s"><span id="mwI_w">edit</span></a><span class="mw-editsection-bracket" id="mwI_0">]</span></span></div>\n<p id="mw7A">The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt180" id="mw7Q" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_{-2} = a"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEWU"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{-2}=a}" id="mwEWY">\n <semantics id="mwEWc">\n <mrow class="MJX-TeXAtom-ORD" id="mwEWg">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEWk">\n <msub id="mwEWo">\n <mi id="mwEWs">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEWw">\n <mo id="mwEW0">−<!-- − --></mo>\n <mn id="mwEW4">2</mn>\n </mrow>\n </msub>\n <mo id="mwEW8">=</mo>\n <mi id="mwEXA">a</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEXE">{\\displaystyle r_{-2}=a}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0136faf86219f470fb2e7ce19768e6cce4444d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.71ex; height:2.009ex;" alt="{\\displaystyle r_{-2}=a}" id="mwEXI"></span> and <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt181" id="mw7g" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_{-1} = b"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEXM"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{-1}=b}" id="mwEXQ">\n <semantics id="mwEXU">\n <mrow class="MJX-TeXAtom-ORD" id="mwEXY">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEXc">\n <msub id="mwEXg">\n <mi id="mwEXk">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEXo">\n <mo id="mwEXs">−<!-- − --></mo>\n <mn id="mwEXw">1</mn>\n </mrow>\n </msub>\n <mo id="mwEX0">=</mo>\n <mi id="mwEX4">b</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEX8">{\\displaystyle r_{-1}=b}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6c050066bdeed7fdaabfe541629f843e6516e1e7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.477ex; height:2.509ex;" alt="{\\displaystyle r_{-1}=b}" id="mwEYA"></span> and will eventually terminate with the integer zero: <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt182" id="mw7w" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{ r_{-2} = a,\\\\ r_{-1} = b,\\\\ r_0,\\\\ r_1,\\\\ \\\\cdots,\\\\ r_{n-1},\\\\ r_n = 0 \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEYE"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{r_{-2}=a,\\ r_{-1}=b,\\ r_{0},\\ r_{1},\\ \\cdots ,\\ r_{n-1},\\ r_{n}=0\\}}" id="mwEYI">\n <semantics id="mwEYM">\n <mrow class="MJX-TeXAtom-ORD" id="mwEYQ">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEYU">\n <mo fence="false" stretchy="false" id="mwEYY">{</mo>\n <msub id="mwEYc">\n <mi id="mwEYg">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEYk">\n <mo id="mwEYo">−<!-- − --></mo>\n <mn id="mwEYs">2</mn>\n </mrow>\n </msub>\n <mo id="mwEYw">=</mo>\n <mi id="mwEY0">a</mi>\n <mo id="mwEY4">,</mo>\n <mtext id="mwEY8"> </mtext>\n <msub id="mwEZA">\n <mi id="mwEZE">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEZI">\n <mo id="mwEZM">−<!-- − --></mo>\n <mn id="mwEZQ">1</mn>\n </mrow>\n </msub>\n <mo id="mwEZU">=</mo>\n <mi id="mwEZY">b</mi>\n <mo id="mwEZc">,</mo>\n <mtext id="mwEZg"> </mtext>\n <msub id="mwEZk">\n <mi id="mwEZo">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEZs">\n <mn id="mwEZw">0</mn>\n </mrow>\n </msub>\n <mo id="mwEZ0">,</mo>\n <mtext id="mwEZ4"> </mtext>\n <msub id="mwEZ8">\n <mi id="mwEaA">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEaE">\n <mn id="mwEaI">1</mn>\n </mrow>\n </msub>\n <mo id="mwEaM">,</mo>\n <mtext id="mwEaQ"> </mtext>\n <mo id="mwEaU">⋯<!-- ⋯ --></mo>\n <mo id="mwEaY">,</mo>\n <mtext id="mwEac"> </mtext>\n <msub id="mwEag">\n <mi id="mwEak">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEao">\n <mi id="mwEas">n</mi>\n <mo id="mwEaw">−<!-- − --></mo>\n <mn id="mwEa0">1</mn>\n </mrow>\n </msub>\n <mo id="mwEa4">,</mo>\n <mtext id="mwEa8"> </mtext>\n <msub id="mwEbA">\n <mi id="mwEbE">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEbI">\n <mi id="mwEbM">n</mi>\n </mrow>\n </msub>\n <mo id="mwEbQ">=</mo>\n <mn id="mwEbU">0</mn>\n <mo fence="false" stretchy="false" id="mwEbY">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEbc">{\\displaystyle \\{r_{-2}=a,\\ r_{-1}=b,\\ r_{0},\\ r_{1},\\ \\cdots ,\\ r_{n-1},\\ r_{n}=0\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/88b215f1f4abd9a17e40896b538e62df052900f9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.798ex; height:2.843ex;" alt="{\\displaystyle \\{r_{-2}=a,\\ r_{-1}=b,\\ r_{0},\\ r_{1},\\ \\cdots ,\\ r_{n-1},\\ r_{n}=0\\}}" id="mwEbg"></span> with <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt183" id="mw8A" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_{k+1} < r_k"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEbk"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{k+1}<r_{k}}" id="mwEbo">\n <semantics id="mwEbs">\n <mrow class="MJX-TeXAtom-ORD" id="mwEbw">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEb0">\n <msub id="mwEb4">\n <mi id="mwEb8">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEcA">\n <mi id="mwEcE">k</mi>\n <mo id="mwEcI">+</mo>\n <mn id="mwEcM">1</mn>\n </mrow>\n </msub>\n <mo id="mwEcQ"><</mo>\n <msub id="mwEcU">\n <mi id="mwEcY">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEcc">\n <mi id="mwEcg">k</mi>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEck">{\\displaystyle r_{k+1}<r_{k}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0050bd8ca461f3a4281bfee17c22e13f42666d44" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.474ex; height:2.176ex;" alt="{\\displaystyle r_{k+1}<r_{k}}" id="mwEco"></span>. The integer <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt184" id="mw8Q" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_{n-1}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEcs"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{n-1}}" id="mwEcw">\n <semantics id="mwEc0">\n <mrow class="MJX-TeXAtom-ORD" id="mwEc4">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEc8">\n <msub id="mwEdA">\n <mi id="mwEdE">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEdI">\n <mi id="mwEdM">n</mi>\n <mo id="mwEdQ">−<!-- − --></mo>\n <mn id="mwEdU">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEdY">{\\displaystyle r_{n-1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1bb9423fd6766c31baf0369064fcf25ea2b1f584" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.368ex; height:2.009ex;" alt="{\\displaystyle r_{n-1}}" id="mwEdc"></span> will then be the GCD and we can state <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt185" id="mw8g" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\text{gcd}(a,b) = r_{n-1}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEdg"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle {\\text{gcd}}(a,b)=r_{n-1}}" id="mwEdk">\n <semantics id="mwEdo">\n <mrow class="MJX-TeXAtom-ORD" id="mwEds">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEdw">\n <mrow class="MJX-TeXAtom-ORD" id="mwEd0">\n <mtext id="mwEd4">gcd</mtext>\n </mrow>\n <mo stretchy="false" id="mwEd8">(</mo>\n <mi id="mwEeA">a</mi>\n <mo id="mwEeE">,</mo>\n <mi id="mwEeI">b</mi>\n <mo stretchy="false" id="mwEeM">)</mo>\n <mo id="mwEeQ">=</mo>\n <msub id="mwEeU">\n <mi id="mwEeY">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEec">\n <mi id="mwEeg">n</mi>\n <mo id="mwEek">−<!-- − --></mo>\n <mn id="mwEeo">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEes">{\\displaystyle {\\text{gcd}}(a,b)=r_{n-1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/96158621032c947e43bfb4c168d7ff905cd33caa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.024ex; height:2.843ex;" alt="{\\displaystyle {\\text{gcd}}(a,b)=r_{n-1}}" id="mwEew"></span>. The algorithm indicates how to construct the intermediate remainders <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt186" id="mw8w" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_k"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEe0"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{k}}" id="mwEe4">\n <semantics id="mwEe8">\n <mrow class="MJX-TeXAtom-ORD" id="mwEfA">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEfE">\n <msub id="mwEfI">\n <mi id="mwEfM">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEfQ">\n <mi id="mwEfU">k</mi>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEfY">{\\displaystyle r_{k}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b28e0e640d099f3676330bd4f604ae15c37bb4f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.137ex; height:2.009ex;" alt="{\\displaystyle r_{k}}" id="mwEfc"></span> via <a rel="mw:WikiLink" href="//en.wikipedia.org/wiki/Euclidean_division" title="Euclidean division" id="mw9A">division-with-remainder</a> on the preceding pair <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt187" id="mw9Q" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"(r_{k-2},\\\\ r_{k-1})"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEfg"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle (r_{k-2},\\ r_{k-1})}" id="mwEfk">\n <semantics id="mwEfo">\n <mrow class="MJX-TeXAtom-ORD" id="mwEfs">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEfw">\n <mo stretchy="false" id="mwEf0">(</mo>\n <msub id="mwEf4">\n <mi id="mwEf8">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEgA">\n <mi id="mwEgE">k</mi>\n <mo id="mwEgI">−<!-- − --></mo>\n <mn id="mwEgM">2</mn>\n </mrow>\n </msub>\n <mo id="mwEgQ">,</mo>\n <mtext id="mwEgU"> </mtext>\n <msub id="mwEgY">\n <mi id="mwEgc">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEgg">\n <mi id="mwEgk">k</mi>\n <mo id="mwEgo">−<!-- − --></mo>\n <mn id="mwEgs">1</mn>\n </mrow>\n </msub>\n <mo stretchy="false" id="mwEgw">)</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEg0">{\\displaystyle (r_{k-2},\\ r_{k-1})}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cd0040f143b057dfaec76c8060a58b9e3c19d52d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.9ex; height:2.843ex;" alt="{\\displaystyle (r_{k-2},\\ r_{k-1})}" id="mwEg4"></span> by finding an integer quotient <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt188" id="mw9g" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"q_k"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEg8"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle q_{k}}" id="mwEhA">\n <semantics id="mwEhE">\n <mrow class="MJX-TeXAtom-ORD" id="mwEhI">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEhM">\n <msub id="mwEhQ">\n <mi id="mwEhU">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEhY">\n <mi id="mwEhc">k</mi>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEhg">{\\displaystyle q_{k}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f27215e46abcad60f100434d2c8003310580af95" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.126ex; height:2.009ex;" alt="{\\displaystyle q_{k}}" id="mwEhk"></span> so that:</p>\n\n<dl id="mw9w"><dd id="mw-A"><span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt190" id="mw-Q" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_{k-2} = q_k \\\\cdot r_{k-1} + r_k \\\\text{, with } \\\\ r_{k-1} > r_k \\\\geq 0."}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEho"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{k-2}=q_{k}\\cdot r_{k-1}+r_{k}{\\text{, with }}\\ r_{k-1}>r_{k}\\geq 0.}" id="mwEhs">\n <semantics id="mwEhw">\n <mrow class="MJX-TeXAtom-ORD" id="mwEh0">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEh4">\n <msub id="mwEh8">\n <mi id="mwEiA">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEiE">\n <mi id="mwEiI">k</mi>\n <mo id="mwEiM">−<!-- − --></mo>\n <mn id="mwEiQ">2</mn>\n </mrow>\n </msub>\n <mo id="mwEiU">=</mo>\n <msub id="mwEiY">\n <mi id="mwEic">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEig">\n <mi id="mwEik">k</mi>\n </mrow>\n </msub>\n <mo id="mwEio">⋅<!-- ⋅ --></mo>\n <msub id="mwEis">\n <mi id="mwEiw">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEi0">\n <mi id="mwEi4">k</mi>\n <mo id="mwEi8">−<!-- − --></mo>\n <mn id="mwEjA">1</mn>\n </mrow>\n </msub>\n <mo id="mwEjE">+</mo>\n <msub id="mwEjI">\n <mi id="mwEjM">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEjQ">\n <mi id="mwEjU">k</mi>\n </mrow>\n </msub>\n <mrow class="MJX-TeXAtom-ORD" id="mwEjY">\n <mtext id="mwEjc">, with </mtext>\n </mrow>\n <mtext id="mwEjg"> </mtext>\n <msub id="mwEjk">\n <mi id="mwEjo">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEjs">\n <mi id="mwEjw">k</mi>\n <mo id="mwEj0">−<!-- − --></mo>\n <mn id="mwEj4">1</mn>\n </mrow>\n </msub>\n <mo id="mwEj8">></mo>\n <msub id="mwEkA">\n <mi id="mwEkE">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEkI">\n <mi id="mwEkM">k</mi>\n </mrow>\n </msub>\n <mo id="mwEkQ">≥<!-- ≥ --></mo>\n <mn id="mwEkU">0.</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEkY">{\\displaystyle r_{k-2}=q_{k}\\cdot r_{k-1}+r_{k}{\\text{, with }}\\ r_{k-1}>r_{k}\\geq 0.}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d63dde782b833a33b8d2da50c06e25e3cf846c7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:43.391ex; height:2.509ex;" alt="{\\displaystyle r_{k-2}=q_{k}\\cdot r_{k-1}+r_{k}{\\text{, with }}\\ r_{k-1}>r_{k}\\geq 0.}" id="mwEkc"></span></dd></dl>\n\n<p id="mw-g">Because the sequence of non-negative integers <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt198" id="mw-w" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{ r_k \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEkg"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{r_{k}\\}}" id="mwEkk">\n <semantics id="mwEko">\n <mrow class="MJX-TeXAtom-ORD" id="mwEks">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEkw">\n <mo fence="false" stretchy="false" id="mwEk0">{</mo>\n <msub id="mwEk4">\n <mi id="mwEk8">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwElA">\n <mi id="mwElE">k</mi>\n </mrow>\n </msub>\n <mo fence="false" stretchy="false" id="mwElI">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwElM">{\\displaystyle \\{r_{k}\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8b17ba8cd3cd568f36a3e47f2d0b1b318e5c2c9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.462ex; height:2.843ex;" alt="{\\displaystyle \\{r_{k}\\}}" id="mwElQ"></span> is strictly decreasing, it eventually <a rel="mw:WikiLink" href="//en.wikipedia.org/wiki/Well-ordering_principle" title="Well-ordering principle" id="mw_A">must terminate</a>. In other words, since <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt199" id="mw_Q" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_k \\\\ge 0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwElU"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{k}\\geq 0}" id="mwElY">\n <semantics id="mwElc">\n <mrow class="MJX-TeXAtom-ORD" id="mwElg">\n <mstyle displaystyle="true" scriptlevel="0" id="mwElk">\n <msub id="mwElo">\n <mi id="mwEls">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwElw">\n <mi id="mwEl0">k</mi>\n </mrow>\n </msub>\n <mo id="mwEl4">≥<!-- ≥ --></mo>\n <mn id="mwEl8">0</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEmA">{\\displaystyle r_{k}\\geq 0}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/88bee94c4dd17b9202cc261159e77292e1a5d535" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.398ex; height:2.509ex;" alt="{\\displaystyle r_{k}\\geq 0}" id="mwEmE"></span> for every <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt200" id="mw_g" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"k"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEmI"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle k}" id="mwEmM">\n <semantics id="mwEmQ">\n <mrow class="MJX-TeXAtom-ORD" id="mwEmU">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEmY">\n <mi id="mwEmc">k</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEmg">{\\displaystyle k}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\\displaystyle k}" id="mwEmk"></span>, and each <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt201" id="mw_w" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_k"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEmo"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{k}}" id="mwEms">\n <semantics id="mwEmw">\n <mrow class="MJX-TeXAtom-ORD" id="mwEm0">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEm4">\n <msub id="mwEm8">\n <mi id="mwEnA">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEnE">\n <mi id="mwEnI">k</mi>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEnM">{\\displaystyle r_{k}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b28e0e640d099f3676330bd4f604ae15c37bb4f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.137ex; height:2.009ex;" alt="{\\displaystyle r_{k}}" id="mwEnQ"></span> is an integer that is strictly smaller than the preceding <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt202" id="mwAQA" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_{k-1}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEnU"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{k-1}}" id="mwEnY">\n <semantics id="mwEnc">\n <mrow class="MJX-TeXAtom-ORD" id="mwEng">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEnk">\n <msub id="mwEno">\n <mi id="mwEns">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEnw">\n <mi id="mwEn0">k</mi>\n <mo id="mwEn4">−<!-- − --></mo>\n <mn id="mwEn8">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEoA">{\\displaystyle r_{k-1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2dbe2626d424eb6b58b44a40172092dc04b16928" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.238ex; height:2.009ex;" alt="{\\displaystyle r_{k-1}}" id="mwEoE"></span>, there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the n-th step with <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt203" id="mwAQE" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_n"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEoI"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{n}}" id="mwEoM">\n <semantics id="mwEoQ">\n <mrow class="MJX-TeXAtom-ORD" id="mwEoU">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEoY">\n <msub id="mwEoc">\n <mi id="mwEog">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEok">\n <mi id="mwEoo">n</mi>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEos">{\\displaystyle r_{n}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57784cdf7f49f2c46baad4eb7b6a7d5c14eb5fa4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.267ex; height:2.009ex;" alt="{\\displaystyle r_{n}}" id="mwEow"></span> equal to zero.<sup about="#mwt205" class="mw-ref reference" id="cite_ref-16" rel="dc:references" typeof="mw:Extension/ref" data-mw="{"name":"ref","attrs":{},"body":{"id":"mw-reference-text-cite_note-16"}}"><a href="#cite_note-16" style="counter-reset: mw-Ref 15;" id="mwAQI"><span class="mw-reflink-text" id="mwAQM">[15]</span></a></sup></p>\n\n<p id="mwAQQ">To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt210" id="mwAQU" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{r_{-2} = 1071,\\\\ r_{-1} = 462 \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEo0"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{r_{-2}=1071,\\ r_{-1}=462\\}}" id="mwEo4">\n <semantics id="mwEo8">\n <mrow class="MJX-TeXAtom-ORD" id="mwEpA">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEpE">\n <mo fence="false" stretchy="false" id="mwEpI">{</mo>\n <msub id="mwEpM">\n <mi id="mwEpQ">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEpU">\n <mo id="mwEpY">−<!-- − --></mo>\n <mn id="mwEpc">2</mn>\n </mrow>\n </msub>\n <mo id="mwEpg">=</mo>\n <mn id="mwEpk">1071</mn>\n <mo id="mwEpo">,</mo>\n <mtext id="mwEps"> </mtext>\n <msub id="mwEpw">\n <mi id="mwEp0">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEp4">\n <mo id="mwEp8">−<!-- − --></mo>\n <mn id="mwEqA">1</mn>\n </mrow>\n </msub>\n <mo id="mwEqE">=</mo>\n <mn id="mwEqI">462</mn>\n <mo fence="false" stretchy="false" id="mwEqM">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEqQ">{\\displaystyle \\{r_{-2}=1071,\\ r_{-1}=462\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d13bb0c5e0679933d256a47f508d4520436a1293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.036ex; height:2.843ex;" alt="{\\displaystyle \\{r_{-2}=1071,\\ r_{-1}=462\\}}" id="mwEqU"></span> and in order to find <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt211" id="mwAQY" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEqY"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{0}}" id="mwEqc">\n <semantics id="mwEqg">\n <mrow class="MJX-TeXAtom-ORD" id="mwEqk">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEqo">\n <msub id="mwEqs">\n <mi id="mwEqw">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEq0">\n <mn id="mwEq4">0</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEq8">{\\displaystyle r_{0}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb12fcfddb65e3d1e6a044215f6e833f0cd4337b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\\displaystyle r_{0}}" id="mwErA"></span>, we need to find integers <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt212" id="mwAQc" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"q_0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwErE"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle q_{0}}" id="mwErI">\n <semantics id="mwErM">\n <mrow class="MJX-TeXAtom-ORD" id="mwErQ">\n <mstyle displaystyle="true" scriptlevel="0" id="mwErU">\n <msub id="mwErY">\n <mi id="mwErc">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwErg">\n <mn id="mwErk">0</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEro">{\\displaystyle q_{0}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d68d37de188ac61f0c0e3f31d5322d1c486f2f4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\\displaystyle q_{0}}" id="mwErs"></span> and <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt213" id="mwAQg" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_0 < r_{-1}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwErw"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{0}<r_{-1}}" id="mwEr0">\n <semantics id="mwEr4">\n <mrow class="MJX-TeXAtom-ORD" id="mwEr8">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEsA">\n <msub id="mwEsE">\n <mi id="mwEsI">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEsM">\n <mn id="mwEsQ">0</mn>\n </mrow>\n </msub>\n <mo id="mwEsU"><</mo>\n <msub id="mwEsY">\n <mi id="mwEsc">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEsg">\n <mo id="mwEsk">−<!-- − --></mo>\n <mn id="mwEso">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEss">{\\displaystyle r_{0}<r_{-1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9881df9fbb3f2e6f2c2ce60f80163ca9c1b79f0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.583ex; height:2.176ex;" alt="{\\displaystyle r_{0}<r_{-1}}" id="mwEsw"></span> such that:</p>\n\n<dl id="mwAQk"><dd id="mwAQo"><span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt215" id="mwAQs" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"1071 = q_0 \\\\cdot 462 + r_0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEs0"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 1071=q_{0}\\cdot 462+r_{0}}" id="mwEs4">\n <semantics id="mwEs8">\n <mrow class="MJX-TeXAtom-ORD" id="mwEtA">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEtE">\n <mn id="mwEtI">1071</mn>\n <mo id="mwEtM">=</mo>\n <msub id="mwEtQ">\n <mi id="mwEtU">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEtY">\n <mn id="mwEtc">0</mn>\n </mrow>\n </msub>\n <mo id="mwEtg">⋅<!-- ⋅ --></mo>\n <mn id="mwEtk">462</mn>\n <mo id="mwEto">+</mo>\n <msub id="mwEts">\n <mi id="mwEtw">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEt0">\n <mn id="mwEt4">0</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEt8">{\\displaystyle 1071=q_{0}\\cdot 462+r_{0}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/134fcdcde86566150a6ea0c4a67edcfa009a104d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.949ex; height:2.509ex;" alt="{\\displaystyle 1071=q_{0}\\cdot 462+r_{0}}" id="mwEuA"></span>.</dd></dl>\n\n<p id="mwAQw">This is the quotient <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt223" id="mwAQ0" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"q_0 = 2"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEuE"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle q_{0}=2}" id="mwEuI">\n <semantics id="mwEuM">\n <mrow class="MJX-TeXAtom-ORD" id="mwEuQ">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEuU">\n <msub id="mwEuY">\n <mi id="mwEuc">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEug">\n <mn id="mwEuk">0</mn>\n </mrow>\n </msub>\n <mo id="mwEuo">=</mo>\n <mn id="mwEus">2</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEuw">{\\displaystyle q_{0}=2}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01aeacf38388c22735226bf7984fa4e0421567a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.352ex; height:2.509ex;" alt="{\\displaystyle q_{0}=2}" id="mwEu0"></span> since <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt224" id="mwAQ4" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"1071 = 2 \\\\cdot 462 + 147"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEu4"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 1071=2\\cdot 462+147}" id="mwEu8">\n <semantics id="mwEvA">\n <mrow class="MJX-TeXAtom-ORD" id="mwEvE">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEvI">\n <mn id="mwEvM">1071</mn>\n <mo id="mwEvQ">=</mo>\n <mn id="mwEvU">2</mn>\n <mo id="mwEvY">⋅<!-- ⋅ --></mo>\n <mn id="mwEvc">462</mn>\n <mo id="mwEvg">+</mo>\n <mn id="mwEvk">147</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEvo">{\\displaystyle 1071=2\\cdot 462+147}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94c999621b3352671d75af5a38849325a1eb48aa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:20.405ex; height:2.343ex;" alt="{\\displaystyle 1071=2\\cdot 462+147}" id="mwEvs"></span>. This determines <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt225" id="mwAQ8" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_0 = 147"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEvw"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{0}=147}" id="mwEv0">\n <semantics id="mwEv4">\n <mrow class="MJX-TeXAtom-ORD" id="mwEv8">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEwA">\n <msub id="mwEwE">\n <mi id="mwEwI">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEwM">\n <mn id="mwEwQ">0</mn>\n </mrow>\n </msub>\n <mo id="mwEwU">=</mo>\n <mn id="mwEwY">147</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEwc">{\\displaystyle r_{0}=147}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5b4e0635872f040ead64628f6a9e9f485f8b2233" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.689ex; height:2.509ex;" alt="{\\displaystyle r_{0}=147}" id="mwEwg"></span> and so the sequence is now <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt226" id="mwARA" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{1071,\\\\ 462,\\\\ r_0 = 147 \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEwk"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{1071,\\ 462,\\ r_{0}=147\\}}" id="mwEwo">\n <semantics id="mwEws">\n <mrow class="MJX-TeXAtom-ORD" id="mwEww">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEw0">\n <mo fence="false" stretchy="false" id="mwEw4">{</mo>\n <mn id="mwEw8">1071</mn>\n <mo id="mwExA">,</mo>\n <mtext id="mwExE"> </mtext>\n <mn id="mwExI">462</mn>\n <mo id="mwExM">,</mo>\n <mtext id="mwExQ"> </mtext>\n <msub id="mwExU">\n <mi id="mwExY">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwExc">\n <mn id="mwExg">0</mn>\n </mrow>\n </msub>\n <mo id="mwExk">=</mo>\n <mn id="mwExo">147</mn>\n <mo fence="false" stretchy="false" id="mwExs">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwExw">{\\displaystyle \\{1071,\\ 462,\\ r_{0}=147\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cdd3b0efd9b16dc223104d6e041f3afba0c06837" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.38ex; height:2.843ex;" alt="{\\displaystyle \\{1071,\\ 462,\\ r_{0}=147\\}}" id="mwEx0"></span>. The next step is to continue the sequence to find <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt227" id="mwARE" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_1"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEx4"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{1}}" id="mwEx8">\n <semantics id="mwEyA">\n <mrow class="MJX-TeXAtom-ORD" id="mwEyE">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEyI">\n <msub id="mwEyM">\n <mi id="mwEyQ">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEyU">\n <mn id="mwEyY">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEyc">{\\displaystyle r_{1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea214f2b31fb3869344bb9311da41c5cc38a99e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\\displaystyle r_{1}}" id="mwEyg"></span> by finding integers <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt228" id="mwARI" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"q_1"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEyk"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle q_{1}}" id="mwEyo">\n <semantics id="mwEys">\n <mrow class="MJX-TeXAtom-ORD" id="mwEyw">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEy0">\n <msub id="mwEy4">\n <mi id="mwEy8">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEzA">\n <mn id="mwEzE">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwEzI">{\\displaystyle q_{1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9daa41f6e8f78ea6bb5711d7ac97901ce564b94e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\\displaystyle q_{1}}" id="mwEzM"></span> and <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt229" id="mwARM" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_1 < r_0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwEzQ"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{1}<r_{0}}" id="mwEzU">\n <semantics id="mwEzY">\n <mrow class="MJX-TeXAtom-ORD" id="mwEzc">\n <mstyle displaystyle="true" scriptlevel="0" id="mwEzg">\n <msub id="mwEzk">\n <mi id="mwEzo">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwEzs">\n <mn id="mwEzw">1</mn>\n </mrow>\n </msub>\n <mo id="mwEz0"><</mo>\n <msub id="mwEz4">\n <mi id="mwEz8">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE0A">\n <mn id="mwE0E">0</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE0I">{\\displaystyle r_{1}<r_{0}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b12c3a286a4d3bb52192f55f84a19d8fd9ddcf15" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.304ex; height:2.176ex;" alt="{\\displaystyle r_{1}<r_{0}}" id="mwE0M"></span> such that:</p>\n\n<dl id="mwARQ"><dd id="mwARU"><span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt231" id="mwARY" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"462 = q_1 \\\\cdot 147 + r_1"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE0Q"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 462=q_{1}\\cdot 147+r_{1}}" id="mwE0U">\n <semantics id="mwE0Y">\n <mrow class="MJX-TeXAtom-ORD" id="mwE0c">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE0g">\n <mn id="mwE0k">462</mn>\n <mo id="mwE0o">=</mo>\n <msub id="mwE0s">\n <mi id="mwE0w">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE00">\n <mn id="mwE04">1</mn>\n </mrow>\n </msub>\n <mo id="mwE08">⋅<!-- ⋅ --></mo>\n <mn id="mwE1A">147</mn>\n <mo id="mwE1E">+</mo>\n <msub id="mwE1I">\n <mi id="mwE1M">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE1Q">\n <mn id="mwE1U">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE1Y">{\\displaystyle 462=q_{1}\\cdot 147+r_{1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb18f88782e8818d4e16a2ac2ac794be65812ddc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.787ex; height:2.509ex;" alt="{\\displaystyle 462=q_{1}\\cdot 147+r_{1}}" id="mwE1c"></span>.</dd></dl>\n\n<p id="mwARc">This is the quotient <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt239" id="mwARg" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"q_1 = 3"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE1g"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle q_{1}=3}" id="mwE1k">\n <semantics id="mwE1o">\n <mrow class="MJX-TeXAtom-ORD" id="mwE1s">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE1w">\n <msub id="mwE10">\n <mi id="mwE14">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE18">\n <mn id="mwE2A">1</mn>\n </mrow>\n </msub>\n <mo id="mwE2E">=</mo>\n <mn id="mwE2I">3</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE2M">{\\displaystyle q_{1}=3}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2a6116e2c4a858aaf540d51e4e66f7ffd71910e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.352ex; height:2.509ex;" alt="{\\displaystyle q_{1}=3}" id="mwE2Q"></span> since <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt240" id="mwARk" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"462 = 3 \\\\cdot 147 + 21"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE2U"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 462=3\\cdot 147+21}" id="mwE2Y">\n <semantics id="mwE2c">\n <mrow class="MJX-TeXAtom-ORD" id="mwE2g">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE2k">\n <mn id="mwE2o">462</mn>\n <mo id="mwE2s">=</mo>\n <mn id="mwE2w">3</mn>\n <mo id="mwE20">⋅<!-- ⋅ --></mo>\n <mn id="mwE24">147</mn>\n <mo id="mwE28">+</mo>\n <mn id="mwE3A">21</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE3E">{\\displaystyle 462=3\\cdot 147+21}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e8dd01e2e052d1e21527bf9cf2ccaa137ad088e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:18.08ex; height:2.343ex;" alt="{\\displaystyle 462=3\\cdot 147+21}" id="mwE3I"></span>. This determines <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt241" id="mwARo" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_1 = 21"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE3M"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{1}=21}" id="mwE3Q">\n <semantics id="mwE3U">\n <mrow class="MJX-TeXAtom-ORD" id="mwE3Y">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE3c">\n <msub id="mwE3g">\n <mi id="mwE3k">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE3o">\n <mn id="mwE3s">1</mn>\n </mrow>\n </msub>\n <mo id="mwE3w">=</mo>\n <mn id="mwE30">21</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE34">{\\displaystyle r_{1}=21}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d76ce06c8842f345132606a468f41bfc181ce02b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.526ex; height:2.509ex;" alt="{\\displaystyle r_{1}=21}" id="mwE38"></span> and so the sequence is now <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt242" id="mwARs" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{1071,\\\\ 462,\\\\ 147,\\\\ r_1 = 21 \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE4A"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{1071,\\ 462,\\ 147,\\ r_{1}=21\\}}" id="mwE4E">\n <semantics id="mwE4I">\n <mrow class="MJX-TeXAtom-ORD" id="mwE4M">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE4Q">\n <mo fence="false" stretchy="false" id="mwE4U">{</mo>\n <mn id="mwE4Y">1071</mn>\n <mo id="mwE4c">,</mo>\n <mtext id="mwE4g"> </mtext>\n <mn id="mwE4k">462</mn>\n <mo id="mwE4o">,</mo>\n <mtext id="mwE4s"> </mtext>\n <mn id="mwE4w">147</mn>\n <mo id="mwE40">,</mo>\n <mtext id="mwE44"> </mtext>\n <msub id="mwE48">\n <mi id="mwE5A">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE5E">\n <mn id="mwE5I">1</mn>\n </mrow>\n </msub>\n <mo id="mwE5M">=</mo>\n <mn id="mwE5Q">21</mn>\n <mo fence="false" stretchy="false" id="mwE5U">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE5Y">{\\displaystyle \\{1071,\\ 462,\\ 147,\\ r_{1}=21\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/377419d7664d8d9ab5a3fe736161190b9d4a14d9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.319ex; height:2.843ex;" alt="{\\displaystyle \\{1071,\\ 462,\\ 147,\\ r_{1}=21\\}}" id="mwE5c"></span>. The next step is to continue the sequence to find <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt243" id="mwARw" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_2"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE5g"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{2}}" id="mwE5k">\n <semantics id="mwE5o">\n <mrow class="MJX-TeXAtom-ORD" id="mwE5s">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE5w">\n <msub id="mwE50">\n <mi id="mwE54">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE58">\n <mn id="mwE6A">2</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE6E">{\\displaystyle r_{2}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cbe9b0b294fdd6fadbf9a7249813f016dcbc44f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\\displaystyle r_{2}}" id="mwE6I"></span> by finding integers <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt244" id="mwAR0" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"q_2"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE6M"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle q_{2}}" id="mwE6Q">\n <semantics id="mwE6U">\n <mrow class="MJX-TeXAtom-ORD" id="mwE6Y">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE6c">\n <msub id="mwE6g">\n <mi id="mwE6k">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE6o">\n <mn id="mwE6s">2</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE6w">{\\displaystyle q_{2}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fd2d05084feb02b8ba29b0673440fb673b102589" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\\displaystyle q_{2}}" id="mwE60"></span> and <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt245" id="mwAR4" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_2 < r_1"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE64"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{2}<r_{1}}" id="mwE68">\n <semantics id="mwE7A">\n <mrow class="MJX-TeXAtom-ORD" id="mwE7E">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE7I">\n <msub id="mwE7M">\n <mi id="mwE7Q">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE7U">\n <mn id="mwE7Y">2</mn>\n </mrow>\n </msub>\n <mo id="mwE7c"><</mo>\n <msub id="mwE7g">\n <mi id="mwE7k">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE7o">\n <mn id="mwE7s">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE7w">{\\displaystyle r_{2}<r_{1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d285ffc35d03cc59b9248ef1aba3aca1db3c1e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.304ex; height:2.176ex;" alt="{\\displaystyle r_{2}<r_{1}}" id="mwE70"></span> such that:</p>\n\n<dl id="mwAR8"><dd id="mwASA"><span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt247" id="mwASE" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"147 = q_2 \\\\cdot 21 + r_2"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE74"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 147=q_{2}\\cdot 21+r_{2}}" id="mwE78">\n <semantics id="mwE8A">\n <mrow class="MJX-TeXAtom-ORD" id="mwE8E">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE8I">\n <mn id="mwE8M">147</mn>\n <mo id="mwE8Q">=</mo>\n <msub id="mwE8U">\n <mi id="mwE8Y">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE8c">\n <mn id="mwE8g">2</mn>\n </mrow>\n </msub>\n <mo id="mwE8k">⋅<!-- ⋅ --></mo>\n <mn id="mwE8o">21</mn>\n <mo id="mwE8s">+</mo>\n <msub id="mwE8w">\n <mi id="mwE80">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE84">\n <mn id="mwE88">2</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE9A">{\\displaystyle 147=q_{2}\\cdot 21+r_{2}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/00aa855c57184d1893bbadf26f03fe81af5f58c1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.624ex; height:2.509ex;" alt="{\\displaystyle 147=q_{2}\\cdot 21+r_{2}}" id="mwE9E"></span>.</dd></dl>\n\n<p id="mwASI">This is the quotient <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt254" id="mwASM" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"q_2 = 7"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE9I"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle q_{2}=7}" id="mwE9M">\n <semantics id="mwE9Q">\n <mrow class="MJX-TeXAtom-ORD" id="mwE9U">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE9Y">\n <msub id="mwE9c">\n <mi id="mwE9g">q</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE9k">\n <mn id="mwE9o">2</mn>\n </mrow>\n </msub>\n <mo id="mwE9s">=</mo>\n <mn id="mwE9w">7</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE90">{\\displaystyle q_{2}=7}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9cedb62a43694c72c63d5111ec2abf553acca77" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.352ex; height:2.509ex;" alt="{\\displaystyle q_{2}=7}" id="mwE94"></span> since <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt255" id="mwASQ" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"147 = 7 \\\\cdot 21 + 0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE98"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 147=7\\cdot 21+0}" id="mwE-A">\n <semantics id="mwE-E">\n <mrow class="MJX-TeXAtom-ORD" id="mwE-I">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE-M">\n <mn id="mwE-Q">147</mn>\n <mo id="mwE-U">=</mo>\n <mn id="mwE-Y">7</mn>\n <mo id="mwE-c">⋅<!-- ⋅ --></mo>\n <mn id="mwE-g">21</mn>\n <mo id="mwE-k">+</mo>\n <mn id="mwE-o">0</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE-s">{\\displaystyle 147=7\\cdot 21+0}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/42e87dc6e6fe5d1f6423040fd2da30926e37a486" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.755ex; height:2.343ex;" alt="{\\displaystyle 147=7\\cdot 21+0}" id="mwE-w"></span>. This determines <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt256" id="mwASU" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_2 = 0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE-0"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{2}=0}" id="mwE-4">\n <semantics id="mwE-8">\n <mrow class="MJX-TeXAtom-ORD" id="mwE_A">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE_E">\n <msub id="mwE_I">\n <mi id="mwE_M">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwE_Q">\n <mn id="mwE_U">2</mn>\n </mrow>\n </msub>\n <mo id="mwE_Y">=</mo>\n <mn id="mwE_c">0</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwE_g">{\\displaystyle r_{2}=0}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/72f6b52dcbeb88769147b35e6edd21b698301547" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.364ex; height:2.509ex;" alt="{\\displaystyle r_{2}=0}" id="mwE_k"></span> and so the sequence is completed as <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt257" id="mwASY" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{1071,\\\\ 462,\\\\ 147,\\\\ 21,\\\\ r_2 = 0 \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwE_o"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{1071,\\ 462,\\ 147,\\ 21,\\ r_{2}=0\\}}" id="mwE_s">\n <semantics id="mwE_w">\n <mrow class="MJX-TeXAtom-ORD" id="mwE_0">\n <mstyle displaystyle="true" scriptlevel="0" id="mwE_4">\n <mo fence="false" stretchy="false" id="mwE_8">{</mo>\n <mn id="mwFAA">1071</mn>\n <mo id="mwFAE">,</mo>\n <mtext id="mwFAI"> </mtext>\n <mn id="mwFAM">462</mn>\n <mo id="mwFAQ">,</mo>\n <mtext id="mwFAU"> </mtext>\n <mn id="mwFAY">147</mn>\n <mo id="mwFAc">,</mo>\n <mtext id="mwFAg"> </mtext>\n <mn id="mwFAk">21</mn>\n <mo id="mwFAo">,</mo>\n <mtext id="mwFAs"> </mtext>\n <msub id="mwFAw">\n <mi id="mwFA0">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFA4">\n <mn id="mwFA8">2</mn>\n </mrow>\n </msub>\n <mo id="mwFBA">=</mo>\n <mn id="mwFBE">0</mn>\n <mo fence="false" stretchy="false" id="mwFBI">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFBM">{\\displaystyle \\{1071,\\ 462,\\ 147,\\ 21,\\ r_{2}=0\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9bf735b01cff1ed6b55ce0abc98f8f2988905728" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.097ex; height:2.843ex;" alt="{\\displaystyle \\{1071,\\ 462,\\ 147,\\ 21,\\ r_{2}=0\\}}" id="mwFBQ"></span> as no further non-negative integer smaller than <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt258" id="mwASc" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFBU"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 0}" id="mwFBY">\n <semantics id="mwFBc">\n <mrow class="MJX-TeXAtom-ORD" id="mwFBg">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFBk">\n <mn id="mwFBo">0</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFBs">{\\displaystyle 0}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\\displaystyle 0}" id="mwFBw"></span> can be found. The penultimate remainder <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt259" id="mwASg" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"21"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFB0"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle 21}" id="mwFB4">\n <semantics id="mwFB8">\n <mrow class="MJX-TeXAtom-ORD" id="mwFCA">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFCE">\n <mn id="mwFCI">21</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFCM">{\\displaystyle 21}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/77ebb9ccf6080ba5c9a6ea8973cb2f26c50211cf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\\displaystyle 21}" id="mwFCQ"></span> is therefore the requested GCD:</p>\n\n<dl id="mwASk"><dd id="mwASo"><span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt261" id="mwASs" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\text{gcd}(1071,\\\\ 462) = 21."}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFCU"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle {\\text{gcd}}(1071,\\ 462)=21.}" id="mwFCY">\n <semantics id="mwFCc">\n <mrow class="MJX-TeXAtom-ORD" id="mwFCg">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFCk">\n <mrow class="MJX-TeXAtom-ORD" id="mwFCo">\n <mtext id="mwFCs">gcd</mtext>\n </mrow>\n <mo stretchy="false" id="mwFCw">(</mo>\n <mn id="mwFC0">1071</mn>\n <mo id="mwFC4">,</mo>\n <mtext id="mwFC8"> </mtext>\n <mn id="mwFDA">462</mn>\n <mo stretchy="false" id="mwFDE">)</mo>\n <mo id="mwFDI">=</mo>\n <mn id="mwFDM">21.</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFDQ">{\\displaystyle {\\text{gcd}}(1071,\\ 462)=21.}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cd300bc3002d80df5682f917dd715d459f8217cc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.119ex; height:2.843ex;" alt="{\\displaystyle {\\text{gcd}}(1071,\\ 462)=21.}" id="mwFDU"></span></dd></dl>\n\n<p id="mwASw">We can generalize slightly by dropping any ordering requirement on the initial two values <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt279" id="mwAS0" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"a"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFDY"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle a}" id="mwFDc">\n <semantics id="mwFDg">\n <mrow class="MJX-TeXAtom-ORD" id="mwFDk">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFDo">\n <mi id="mwFDs">a</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFDw">{\\displaystyle a}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\\displaystyle a}" id="mwFD0"></span> and <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt280" id="mwAS4" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"b"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFD4"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle b}" id="mwFD8">\n <semantics id="mwFEA">\n <mrow class="MJX-TeXAtom-ORD" id="mwFEE">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFEI">\n <mi id="mwFEM">b</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFEQ">{\\displaystyle b}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\\displaystyle b}" id="mwFEU"></span>. If <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt281" id="mwAS8" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"a = b"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFEY"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle a=b}" id="mwFEc">\n <semantics id="mwFEg">\n <mrow class="MJX-TeXAtom-ORD" id="mwFEk">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFEo">\n <mi id="mwFEs">a</mi>\n <mo id="mwFEw">=</mo>\n <mi id="mwFE0">b</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFE4">{\\displaystyle a=b}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1956b03d1314c7071ac1f45ed7b1e29422dcfcc4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\\displaystyle a=b}" id="mwFE8"></span>, the algorithm may continue and trivially find that <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt282" id="mwATA" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\text{gcd}(a,\\\\ a) = a"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFFA"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle {\\text{gcd}}(a,\\ a)=a}" id="mwFFE">\n <semantics id="mwFFI">\n <mrow class="MJX-TeXAtom-ORD" id="mwFFM">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFFQ">\n <mrow class="MJX-TeXAtom-ORD" id="mwFFU">\n <mtext id="mwFFY">gcd</mtext>\n </mrow>\n <mo stretchy="false" id="mwFFc">(</mo>\n <mi id="mwFFg">a</mi>\n <mo id="mwFFk">,</mo>\n <mtext id="mwFFo"> </mtext>\n <mi id="mwFFs">a</mi>\n <mo stretchy="false" id="mwFFw">)</mo>\n <mo id="mwFF0">=</mo>\n <mi id="mwFF4">a</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFF8">{\\displaystyle {\\text{gcd}}(a,\\ a)=a}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fad3c75dee86381c3e7294b138cb04e32fe73783" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.699ex; height:2.843ex;" alt="{\\displaystyle {\\text{gcd}}(a,\\ a)=a}" id="mwFGA"></span> as the sequence of remainders will be <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt283" id="mwATE" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{a,\\\\ a,\\\\ 0\\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFGE"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{a,\\ a,\\ 0\\}}" id="mwFGI">\n <semantics id="mwFGM">\n <mrow class="MJX-TeXAtom-ORD" id="mwFGQ">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFGU">\n <mo fence="false" stretchy="false" id="mwFGY">{</mo>\n <mi id="mwFGc">a</mi>\n <mo id="mwFGg">,</mo>\n <mtext id="mwFGk"> </mtext>\n <mi id="mwFGo">a</mi>\n <mo id="mwFGs">,</mo>\n <mtext id="mwFGw"> </mtext>\n <mn id="mwFG0">0</mn>\n <mo fence="false" stretchy="false" id="mwFG4">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFG8">{\\displaystyle \\{a,\\ a,\\ 0\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0dd9b227019fa9774e888298439ac8590061ed13" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.176ex; height:2.843ex;" alt="{\\displaystyle \\{a,\\ a,\\ 0\\}}" id="mwFHA"></span>. If <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt284" id="mwATI" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"a < b"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFHE"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle a<b}" id="mwFHI">\n <semantics id="mwFHM">\n <mrow class="MJX-TeXAtom-ORD" id="mwFHQ">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFHU">\n <mi id="mwFHY">a</mi>\n <mo id="mwFHc"><</mo>\n <mi id="mwFHg">b</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFHk">{\\displaystyle a<b}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/91a7698e4c7401bb321f97888b872b583a9e4642" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\\displaystyle a<b}" id="mwFHo"></span>, then we can also continue since <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt285" id="mwATM" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"a \\\\equiv 0 \\\\cdot b + a"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFHs"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle a\\equiv 0\\cdot b+a}" id="mwFHw">\n <semantics id="mwFH0">\n <mrow class="MJX-TeXAtom-ORD" id="mwFH4">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFH8">\n <mi id="mwFIA">a</mi>\n <mo id="mwFIE">≡<!-- ≡ --></mo>\n <mn id="mwFII">0</mn>\n <mo id="mwFIM">⋅<!-- ⋅ --></mo>\n <mi id="mwFIQ">b</mi>\n <mo id="mwFIU">+</mo>\n <mi id="mwFIY">a</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFIc">{\\displaystyle a\\equiv 0\\cdot b+a}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fc32682dc755734e0b01e1fc2e0cbb81e1b9e1b4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.238ex; height:2.343ex;" alt="{\\displaystyle a\\equiv 0\\cdot b+a}" id="mwFIg"></span>, suggesting the next remainder should be <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt286" id="mwATQ" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"a"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFIk"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle a}" id="mwFIo">\n <semantics id="mwFIs">\n <mrow class="MJX-TeXAtom-ORD" id="mwFIw">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFI0">\n <mi id="mwFI4">a</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFI8">{\\displaystyle a}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\\displaystyle a}" id="mwFJA"></span> itself, and the sequence is <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt287" id="mwATU" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{a,\\\\ b,\\\\ a,\\\\ \\\\cdots \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFJE"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{a,\\ b,\\ a,\\ \\cdots \\}}" id="mwFJI">\n <semantics id="mwFJM">\n <mrow class="MJX-TeXAtom-ORD" id="mwFJQ">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFJU">\n <mo fence="false" stretchy="false" id="mwFJY">{</mo>\n <mi id="mwFJc">a</mi>\n <mo id="mwFJg">,</mo>\n <mtext id="mwFJk"> </mtext>\n <mi id="mwFJo">b</mi>\n <mo id="mwFJs">,</mo>\n <mtext id="mwFJw"> </mtext>\n <mi id="mwFJ0">a</mi>\n <mo id="mwFJ4">,</mo>\n <mtext id="mwFJ8"> </mtext>\n <mo id="mwFKA">⋯<!-- ⋯ --></mo>\n <mo fence="false" stretchy="false" id="mwFKE">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFKI">{\\displaystyle \\{a,\\ b,\\ a,\\ \\cdots \\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/13e8ec985de11109fdd5ef818058b27c909f3222" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.736ex; height:2.843ex;" alt="{\\displaystyle \\{a,\\ b,\\ a,\\ \\cdots \\}}" id="mwFKM"></span>. Normally, this would be invalid because it breaks the requirement <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt288" id="mwATY" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_0 < r_{-1}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFKQ"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{0}<r_{-1}}" id="mwFKU">\n <semantics id="mwFKY">\n <mrow class="MJX-TeXAtom-ORD" id="mwFKc">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFKg">\n <msub id="mwFKk">\n <mi id="mwFKo">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFKs">\n <mn id="mwFKw">0</mn>\n </mrow>\n </msub>\n <mo id="mwFK0"><</mo>\n <msub id="mwFK4">\n <mi id="mwFK8">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFLA">\n <mo id="mwFLE">−<!-- − --></mo>\n <mn id="mwFLI">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFLM">{\\displaystyle r_{0}<r_{-1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9881df9fbb3f2e6f2c2ce60f80163ca9c1b79f0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.583ex; height:2.176ex;" alt="{\\displaystyle r_{0}<r_{-1}}" id="mwFLQ"></span> but now we have <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt289" id="mwATc" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"a < b"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFLU"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle a<b}" id="mwFLY">\n <semantics id="mwFLc">\n <mrow class="MJX-TeXAtom-ORD" id="mwFLg">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFLk">\n <mi id="mwFLo">a</mi>\n <mo id="mwFLs"><</mo>\n <mi id="mwFLw">b</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFL0">{\\displaystyle a<b}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/91a7698e4c7401bb321f97888b872b583a9e4642" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\\displaystyle a<b}" id="mwFL4"></span> by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt290" id="mwATg" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_0 < b"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFL8"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{0}<b}" id="mwFMA">\n <semantics id="mwFME">\n <mrow class="MJX-TeXAtom-ORD" id="mwFMI">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFMM">\n <msub id="mwFMQ">\n <mi id="mwFMU">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFMY">\n <mn id="mwFMc">0</mn>\n </mrow>\n </msub>\n <mo id="mwFMg"><</mo>\n <mi id="mwFMk">b</mi>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFMo">{\\displaystyle r_{0}<b}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cee19f7a6468daf3449129c0da9cd74c60907870" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.199ex; height:2.509ex;" alt="{\\displaystyle r_{0}<b}" id="mwFMs"></span> and everything continues as above. The only modifications that need to be made are that <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt291" id="mwATk" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"r_{k} < r_{k-1}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFMw"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle r_{k}<r_{k-1}}" id="mwFM0">\n <semantics id="mwFM4">\n <mrow class="MJX-TeXAtom-ORD" id="mwFM8">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFNA">\n <msub id="mwFNE">\n <mi id="mwFNI">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFNM">\n <mi id="mwFNQ">k</mi>\n </mrow>\n </msub>\n <mo id="mwFNU"><</mo>\n <msub id="mwFNY">\n <mi id="mwFNc">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFNg">\n <mi id="mwFNk">k</mi>\n <mo id="mwFNo">−<!-- − --></mo>\n <mn id="mwFNs">1</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFNw">{\\displaystyle r_{k}<r_{k-1}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7fef79fa31424b1f2f75ab8680ce6c99967dd167" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.474ex; height:2.176ex;" alt="{\\displaystyle r_{k}<r_{k-1}}" id="mwFN0"></span> only for <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt292" id="mwATo" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"k \\\\ge 0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFN4"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle k\\geq 0}" id="mwFN8">\n <semantics id="mwFOA">\n <mrow class="MJX-TeXAtom-ORD" id="mwFOE">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFOI">\n <mi id="mwFOM">k</mi>\n <mo id="mwFOQ">≥<!-- ≥ --></mo>\n <mn id="mwFOU">0</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFOY">{\\displaystyle k\\geq 0}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/79214ef55efadfb1d9c9b02252eb8a71cf6f8b6b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\\displaystyle k\\geq 0}" id="mwFOc"></span>, and that the sub-sequence of non-negative integers <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt293" id="mwATs" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"\\\\{ r_{k-1} \\\\}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFOg"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle \\{r_{k-1}\\}}" id="mwFOk">\n <semantics id="mwFOo">\n <mrow class="MJX-TeXAtom-ORD" id="mwFOs">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFOw">\n <mo fence="false" stretchy="false" id="mwFO0">{</mo>\n <msub id="mwFO4">\n <mi id="mwFO8">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFPA">\n <mi id="mwFPE">k</mi>\n <mo id="mwFPI">−<!-- − --></mo>\n <mn id="mwFPM">1</mn>\n </mrow>\n </msub>\n <mo fence="false" stretchy="false" id="mwFPQ">}</mo>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFPU">{\\displaystyle \\{r_{k-1}\\}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f241182d363fb5368558a99442e54504cb2a065" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.563ex; height:2.843ex;" alt="{\\displaystyle \\{r_{k-1}\\}}" id="mwFPY"></span> for <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt294" id="mwATw" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"k \\\\ge 0"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFPc"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle k\\geq 0}" id="mwFPg">\n <semantics id="mwFPk">\n <mrow class="MJX-TeXAtom-ORD" id="mwFPo">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFPs">\n <mi id="mwFPw">k</mi>\n <mo id="mwFP0">≥<!-- ≥ --></mo>\n <mn id="mwFP4">0</mn>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFP8">{\\displaystyle k\\geq 0}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/79214ef55efadfb1d9c9b02252eb8a71cf6f8b6b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\\displaystyle k\\geq 0}" id="mwFQA"></span> is strictly decreasing, therefore excluding <span class="mwe-math-element" typeof="mw:Extension/math" about="#mwt295" id="mwAT0" data-mw="{"name":"math","attrs":{},"body":{"extsrc":"a = r_{-2}"}}"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;" id="mwFQE"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\\displaystyle a=r_{-2}}" id="mwFQI">\n <semantics id="mwFQM">\n <mrow class="MJX-TeXAtom-ORD" id="mwFQQ">\n <mstyle displaystyle="true" scriptlevel="0" id="mwFQU">\n <mi id="mwFQY">a</mi>\n <mo id="mwFQc">=</mo>\n <msub id="mwFQg">\n <mi id="mwFQk">r</mi>\n <mrow class="MJX-TeXAtom-ORD" id="mwFQo">\n <mo id="mwFQs">−<!-- − --></mo>\n <mn id="mwFQw">2</mn>\n </mrow>\n </msub>\n </mstyle>\n </mrow>\n <annotation encoding="application/x-tex" id="mwFQ0">{\\displaystyle a=r_{-2}}</annotation>\n </semantics>\n</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/965ed3d75ce7948e5fe434ec6f79dcbaf252b119" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.71ex; height:2.009ex;" alt="{\\displaystyle a=r_{-2}}" id="mwFQ4"></span> from both statements.</p>\n\n
</section>
</div>