Felix' Math Place (Posts about greatest common divisor.)
https://math.fontein.de/tag/greatest-common-divisor.atom
2019-11-17T10:38:18Z
Felix Fontein
Nikola
Euclidean Domains, and the Extended Euclidean Algorithm.
https://math.fontein.de/2009/11/18/euclidean-domains-and-the-extended-euclidean-algorithm/
2009-11-18T02:34:06+01:00
2009-11-18T02:34:06+01:00
Felix Fontein
<div>
<p>
In this post, I want to sum up some handy results concerning the Extended Euclidean Algorithm. For that, let <span class="inline-formula"><img class="img-inline-formula img-formula" width="44" height="18" src="https://math.fontein.de/formulae/x7OzSY_oDRbER5oYIxl2jbuuiuNl74yHBX8IrA.svgz" alt="(R, d)" title="(R, d)"></span> be an Euclidean domain:
</p>
<div class="theorem-environment theorem-definition-environment">
<div class="theorem-header theorem-definition-header">
Definition.
</div>
<div class="theorem-content theorem-definition-content">
<p>
An <em>Euclidean domain</em> is an integral domain <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/vYu2wcShMlDKJ.IrmXbb2no6ZOHI_2bIn_7ZWQ.svgz" alt="R" title="R"></span> together with a function <span class="inline-formula"><img class="img-inline-formula img-formula" width="140" height="18" src="https://math.fontein.de/formulae/3_BSL3h.5yMQz5zF9hhTejjza7Bvz3XCpZt6Pw.svgz" alt="d : R \setminus \{ 0 \} \to \N_{>0}" title="d : R \setminus \{ 0 \} \to \N_{>0}"></span> satisfying, if <span class="inline-formula"><img class="img-inline-formula img-formula" width="69" height="18" src="https://math.fontein.de/formulae/XSxY6L3ifEz._CIJkNDN5wgK5mCXuWgOzQoAxQ.svgz" alt="d(0) := 0" title="d(0) := 0"></span>, that for every <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="16" src="https://math.fontein.de/formulae/MD4.T1gT6j1FBZpVeTmzuidaegYvMair7zg9fg.svgz" alt="a, b\in R" title="a, b\in R"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="40" height="16" src="https://math.fontein.de/formulae/vQEhWqcf0URCoLapqQSLHWiUU_Bwf0OJZC7vMg.svgz" alt="b \neq 0" title="b \neq 0"></span> there exist <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="16" src="https://math.fontein.de/formulae/s9cA9.ahzSqmWkfb3ASb5eBb3tgPPBAYb1XHvQ.svgz" alt="q, r \in R" title="q, r \in R"></span> such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="79" height="16" src="https://math.fontein.de/formulae/Iz6QryYjEkFoZLQqQAcSTFq4Ry.7N5dcFbaPbA.svgz" alt="a = q b + r" title="a = q b + r"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="86" height="18" src="https://math.fontein.de/formulae/VV4.jOEnP0Z5sUZ237sb1s6rITySbjCxLaw1qw.svgz" alt="d(r) < d(b)" title="d(r) < d(b)"></span>.
</p>
</div>
</div>
<p>
First, note that we can modify the map <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="12" src="https://math.fontein.de/formulae/DxlmDzniFM_09XzQnKCoRu8h2JBxVd5JriHzmg.svgz" alt="d" title="d"></span> to provide an additional property:
</p>
<div class="theorem-environment theorem-proposition-environment">
<div class="theorem-header theorem-proposition-header">
Proposition.
</div>
<div class="theorem-content theorem-proposition-content">
<p>
Define <span class="inline-formula"><img class="img-inline-formula img-formula" width="97" height="22" src="https://math.fontein.de/formulae/1hbOZn02NmTMfCmiGAQfPwoZ3wpPg6hDQUnm_Q.svgz" alt="\hat{d} : R \to \N_{\ge 0}" title="\hat{d} : R \to \N_{\ge 0}"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="162" height="20" src="https://math.fontein.de/formulae/UgfgTccmPqCm.KYBMtyckRVBwvhYXm4OFKuLSg.svgz" alt="x \mapsto \inf_{y \in R \setminus \{ 0 \}} d(x y)" title="x \mapsto \inf_{y \in R \setminus \{ 0 \}} d(x y)"></span>. Then <span class="inline-formula"><img class="img-inline-formula img-formula" width="44" height="21" src="https://math.fontein.de/formulae/ANED77RhwDLNKXm7kXAQEXjPXFKVJgblMuclMA.svgz" alt="(R, \hat{d})" title="(R, \hat{d})"></span> is an Euclidean domain satisfying <span class="inline-formula"><img class="img-inline-formula img-formula" width="96" height="21" src="https://math.fontein.de/formulae/KTCin5qb2qkoekBmQLUQKRYnX4hQY0gfM_7Big.svgz" alt="\hat{d}(a) \le \hat{d}(a b)" title="\hat{d}(a) \le \hat{d}(a b)"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="103" height="18" src="https://math.fontein.de/formulae/J4cxOoQ5VhbcAB4shy77L1BKChULKDB_JQwqSw.svgz" alt="a, b \in R \setminus \{ 0 \}" title="a, b \in R \setminus \{ 0 \}"></span>.
</p>
</div>
</div>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof.
</div>
<div class="theorem-content theorem-proof-content">
<p>
First, <span class="inline-formula"><img class="img-inline-formula img-formula" width="66" height="21" src="https://math.fontein.de/formulae/DuMR9A3V_ubx5pSIvGEOshq5bb5W65cmW8xKWQ.svgz" alt="\hat{d}(x) = 0" title="\hat{d}(x) = 0"></span> if, and only if, <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="11" src="https://math.fontein.de/formulae/GDv2K9YNvA3j0.yxpqdxaQAdP78782LTKgUQdw.svgz" alt="x = 0" title="x = 0"></span>. Next, <span class="inline-formula"><img class="img-inline-formula img-formula" width="104" height="21" src="https://math.fontein.de/formulae/BLPhJ1NZiQOiuJWldkcu5UANWZoqwN_PdMugBQ.svgz" alt="\hat{d}(a) \le d(a b c)" title="\hat{d}(a) \le d(a b c)"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="13" src="https://math.fontein.de/formulae/VtY6khvUrjGGFcHxth4B1wLm_yJQd3ZlZJMHKg.svgz" alt="c \in R" title="c \in R"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="96" height="21" src="https://math.fontein.de/formulae/KTCin5qb2qkoekBmQLUQKRYnX4hQY0gfM_7Big.svgz" alt="\hat{d}(a) \le \hat{d}(a b)" title="\hat{d}(a) \le \hat{d}(a b)"></span>.
</p>
<p>
Now, let <span class="inline-formula"><img class="img-inline-formula img-formula" width="25" height="16" src="https://math.fontein.de/formulae/JxPYhIthoRSykB31vDh_9r8gZWwR1Q11Zd9oHw.svgz" alt="a, b" title="a, b"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="40" height="16" src="https://math.fontein.de/formulae/vQEhWqcf0URCoLapqQSLHWiUU_Bwf0OJZC7vMg.svgz" alt="b \neq 0" title="b \neq 0"></span>. Let <span class="inline-formula"><img class="img-inline-formula img-formula" width="89" height="18" src="https://math.fontein.de/formulae/skciBGoLR1GDsz0uYx7dXugFhlleVhLsjeytrA.svgz" alt="x \in R \setminus \{ 0 \}" title="x \in R \setminus \{ 0 \}"></span> be such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="95" height="21" src="https://math.fontein.de/formulae/XUZdwlTuLQzR3iOg_0_eqxZsDu2oWR9jOZ2bsw.svgz" alt="d(b x) = \hat{d}(b)" title="d(b x) = \hat{d}(b)"></span>. Now let <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="16" src="https://math.fontein.de/formulae/s9cA9.ahzSqmWkfb3ASb5eBb3tgPPBAYb1XHvQ.svgz" alt="q, r \in R" title="q, r \in R"></span> be with <span class="inline-formula"><img class="img-inline-formula img-formula" width="113" height="18" src="https://math.fontein.de/formulae/UtwJ5EpUJRK6IhsPi.h4Ovy_FcbIPLBXq1PK8Q.svgz" alt="a x = q (b x) + r" title="a x = q (b x) + r"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="96" height="18" src="https://math.fontein.de/formulae/f972C0ytdzU9kdXpJEhWbXASe2lLwEaf4vA22g.svgz" alt="d(r) < d(b x)" title="d(r) < d(b x)"></span>. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="103" height="18" src="https://math.fontein.de/formulae/UQgInA9d8yGwrlrzHMybcbKxByVwFrv2iRWcIg.svgz" alt="r = (a - q b) x" title="r = (a - q b) x"></span>, there is an <span class="inline-formula"><img class="img-inline-formula img-formula" width="49" height="14" src="https://math.fontein.de/formulae/.n335UyCK_RucDrF9j2q2c4f2vOW6FggvHS6Jw.svgz" alt="r' \in R" title="r' \in R"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="56" height="13" src="https://math.fontein.de/formulae/ICoGRgBcdOpGoUKzah7nsFRa8Q8V1mqDbpnd5w.svgz" alt="r = r' x" title="r = r' x"></span>. Now
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="340" height="21" src="https://math.fontein.de/formulae/7nMK19Sije9J3RQPqtPZpzIDOqlpV7IUHTHIZQ.svgz" alt="\hat{d}(r') \le \hat{d}(r' x) = \hat{d}(r) \le d(r) < d(b x) = \hat{d}(b)," title="\hat{d}(r') \le \hat{d}(r' x) = \hat{d}(r) \le d(r) < d(b x) = \hat{d}(b),">
</div>
<p>
and <span class="inline-formula"><img class="img-inline-formula img-formula" width="84" height="17" src="https://math.fontein.de/formulae/rN_U.3mNeyRurbWJULmoEM8DOqBVhPsJSJfxRg.svgz" alt="a = q b + r'" title="a = q b + r'"></span>.
</p>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
<p>
This new map <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="17" src="https://math.fontein.de/formulae/_BExrBfAd1b0zRGQO4WyFZqWCrebxv0g8MTqWg.svgz" alt="\hat{d}" title="\hat{d}"></span> satisfies three nice properties:
</p>
<div class="theorem-environment theorem-lemma-environment">
<div class="theorem-header theorem-lemma-header">
Lemma.
</div>
<div class="theorem-content theorem-lemma-content">
<ol class="enum-level-1">
<li>We have <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="21" src="https://math.fontein.de/formulae/O.whvrldiBhc4dEyTSCGoNG3NBcdc60Wg9kBsg.svgz" alt="\hat{d}(1) \le \hat{d}(a)" title="\hat{d}(1) \le \hat{d}(a)"></span> for every <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/W0u29wE2nStBaHGm8KBURCGMZ__5QHS5z1rtrw.svgz" alt="a \in R \setminus \{ 0 \}" title="a \in R \setminus \{ 0 \}"></span>.</li>
<li>For <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/W0u29wE2nStBaHGm8KBURCGMZ__5QHS5z1rtrw.svgz" alt="a \in R \setminus \{ 0 \}" title="a \in R \setminus \{ 0 \}"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="21" src="https://math.fontein.de/formulae/lHth56j47tZ0loF5BjYAdlcxUJlzdi4f7UOK5A.svgz" alt="\hat{d}(a) = \hat{d}(1)" title="\hat{d}(a) = \hat{d}(1)"></span> if, and only if, <span class="inline-formula"><img class="img-inline-formula img-formula" width="53" height="13" src="https://math.fontein.de/formulae/9MmHOgkYGouigcpPQIsbcMGWQpEq4eU94MXSmQ.svgz" alt="a \in R^*" title="a \in R^*"></span>.</li>
<li>If <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="18" src="https://math.fontein.de/formulae/8GreiQfrAMu_QvUr9diqY4i8pKaJt.43Je4COQ.svgz" alt="(a) = (b)" title="(a) = (b)"></span>, then <span class="inline-formula"><img class="img-inline-formula img-formula" width="87" height="21" src="https://math.fontein.de/formulae/7xxSq.wwU8EUSBeXP0jYcg7JXiyO6sQu1nKsKA.svgz" alt="\hat{d}(a) = \hat{d}(b)" title="\hat{d}(a) = \hat{d}(b)"></span>.</li>
</ol>
</div>
</div>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof.
</div>
<div class="theorem-content theorem-proof-content">
<ol class="enum-level-1">
<li>For <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/W0u29wE2nStBaHGm8KBURCGMZ__5QHS5z1rtrw.svgz" alt="a \in R \setminus \{ 0 \}" title="a \in R \setminus \{ 0 \}"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="165" height="21" src="https://math.fontein.de/formulae/x5hMlE8iyATBvsJyw1GQLM17BmxllA0zGSGOZQ.svgz" alt="d(1) \le \hat{d}(1 \cdot a) = \hat{d}(a)" title="d(1) \le \hat{d}(1 \cdot a) = \hat{d}(a)"></span>.</li>
<li>
<p>
First, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="53" height="13" src="https://math.fontein.de/formulae/9MmHOgkYGouigcpPQIsbcMGWQpEq4eU94MXSmQ.svgz" alt="a \in R^*" title="a \in R^*"></span>. Then
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="311" height="21" src="https://math.fontein.de/formulae/1_nZajg2BieA.YujVDoYM7wRgra10iw1R0NahQ.svgz" alt="\hat{d}(a) \le \hat{d}(a a^{-1}) = \hat{d}(1) \le \hat{d}(1 \cdot a) = \hat{d}(a)," title="\hat{d}(a) \le \hat{d}(a a^{-1}) = \hat{d}(1) \le \hat{d}(1 \cdot a) = \hat{d}(a),">
</div>
<p>
whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="21" src="https://math.fontein.de/formulae/lHth56j47tZ0loF5BjYAdlcxUJlzdi4f7UOK5A.svgz" alt="\hat{d}(a) = \hat{d}(1)" title="\hat{d}(a) = \hat{d}(1)"></span>.
</p>
<p>
Now, conversely, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="21" src="https://math.fontein.de/formulae/lHth56j47tZ0loF5BjYAdlcxUJlzdi4f7UOK5A.svgz" alt="\hat{d}(a) = \hat{d}(1)" title="\hat{d}(a) = \hat{d}(1)"></span>. Write <span class="inline-formula"><img class="img-inline-formula img-formula" width="80" height="15" src="https://math.fontein.de/formulae/0HoXNMvH9kwiEm1of4mFr2IFyiCNwZb17Mx24g.svgz" alt="1 = q a + r" title="1 = q a + r"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="16" src="https://math.fontein.de/formulae/s9cA9.ahzSqmWkfb3ASb5eBb3tgPPBAYb1XHvQ.svgz" alt="q, r \in R" title="q, r \in R"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="143" height="21" src="https://math.fontein.de/formulae/2driH7E51_VInxDbwhIbQpMZR02cmV.wHQeT7g.svgz" alt="\hat{d}(r) < \hat{d}(a) = \hat{d}(1)" title="\hat{d}(r) < \hat{d}(a) = \hat{d}(1)"></span>. By 1., we get <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="11" src="https://math.fontein.de/formulae/7xNxpr3R49Q.4cLaK6bH0Avb9HKGrYQi4CuoPQ.svgz" alt="r = 0" title="r = 0"></span>. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="15" src="https://math.fontein.de/formulae/2IutKKq8osNrlHLiYwwRe3pt6U_H68KZUKDrvA.svgz" alt="1 = q a" title="1 = q a"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="53" height="13" src="https://math.fontein.de/formulae/9MmHOgkYGouigcpPQIsbcMGWQpEq4eU94MXSmQ.svgz" alt="a \in R^*" title="a \in R^*"></span>.
</p>
</li>
<li>
<p>
As <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/vYu2wcShMlDKJ.IrmXbb2no6ZOHI_2bIn_7ZWQ.svgz" alt="R" title="R"></span> is an integral domain, <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="18" src="https://math.fontein.de/formulae/8GreiQfrAMu_QvUr9diqY4i8pKaJt.43Je4COQ.svgz" alt="(a) = (b)" title="(a) = (b)"></span> implies <span class="inline-formula"><img class="img-inline-formula img-formula" width="51" height="12" src="https://math.fontein.de/formulae/x9l8QGktPDbgO9KthJOJeRdakLOOM1okfRZBTg.svgz" alt="a = b u" title="a = b u"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="54" height="13" src="https://math.fontein.de/formulae/0SG7zbQBU3lRHpcIh4aH4F4WRrgQ0ow876n9sQ.svgz" alt="u \in R^*" title="u \in R^*"></span>. But then
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="327" height="52" src="https://math.fontein.de/formulae/LQr867a3Pz4AK6UzaSsjdvvlKBLdHsD1p5YcAg.svgz" alt="\hat{d}(a) \le{} & \hat{d}(b u) \le \hat{d}(b u u^{-1}) \\
{}={} & \hat{d}(b) \le \hat{d}(a u^{-1}) \le \hat{d}(a u^{-1} u) = \hat{d}(a)," title="\hat{d}(a) \le{} & \hat{d}(b u) \le \hat{d}(b u u^{-1}) \\
{}={} & \hat{d}(b) \le \hat{d}(a u^{-1}) \le \hat{d}(a u^{-1} u) = \hat{d}(a),">
</div>
<p>
i.e. <span class="inline-formula"><img class="img-inline-formula img-formula" width="87" height="21" src="https://math.fontein.de/formulae/7xxSq.wwU8EUSBeXP0jYcg7JXiyO6sQu1nKsKA.svgz" alt="\hat{d}(a) = \hat{d}(b)" title="\hat{d}(a) = \hat{d}(b)"></span>.
</p>
</li>
</ol>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
<p>
From now on, we <strong>assume</strong> that <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="12" src="https://math.fontein.de/formulae/DxlmDzniFM_09XzQnKCoRu8h2JBxVd5JriHzmg.svgz" alt="d" title="d"></span> has the property <span class="inline-formula"><img class="img-inline-formula img-formula" width="96" height="18" src="https://math.fontein.de/formulae/qXBHCmvBYhzAqvLOfFJMB0V0Je4uZP7mS3JR.Q.svgz" alt="d(a) \le d(a b)" title="d(a) \le d(a b)"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="16" src="https://math.fontein.de/formulae/BKHzTmQHrr.6UYl.goLGl6zjuc.8tW3k6zxpYA.svgz" alt="a, b \in R" title="a, b \in R"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="40" height="16" src="https://math.fontein.de/formulae/vQEhWqcf0URCoLapqQSLHWiUU_Bwf0OJZC7vMg.svgz" alt="b \neq 0" title="b \neq 0"></span>.
</p>
<p>
There are two important examples of Euclidean domains, both of them satisfying <span class="inline-formula"><img class="img-inline-formula img-formula" width="127" height="18" src="https://math.fontein.de/formulae/gR3BysF730IKIbu5k1SUMF4pAQRbq2yDzldzFA.svgz" alt="d(a b) = d(a) d(b)" title="d(a b) = d(a) d(b)"></span>, which in turn implies <span class="inline-formula"><img class="img-inline-formula img-formula" width="96" height="18" src="https://math.fontein.de/formulae/BNOWCdX.FD2jhnhx4jCN4NOhKW8hTmJ.H_E7gw.svgz" alt="d(a b) \ge d(a)" title="d(a b) \ge d(a)"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="40" height="16" src="https://math.fontein.de/formulae/vQEhWqcf0URCoLapqQSLHWiUU_Bwf0OJZC7vMg.svgz" alt="b \neq 0" title="b \neq 0"></span>:
</p>
<ol class="enum-level-1">
<li>The integers <span class="inline-formula"><img class="img-inline-formula img-formula" width="54" height="12" src="https://math.fontein.de/formulae/ck2hjLPq7tHaxh1uvokRiwREEUG0hdOhLb6T9g.svgz" alt="R := \Z" title="R := \Z"></span> form an Euclidean ring with <span class="inline-formula"><img class="img-inline-formula img-formula" width="80" height="18" src="https://math.fontein.de/formulae/cGN0D1UeHylPPgIf4wmcuT1lhOypRccdYdY5yQ.svgz" alt="d(a) := \abs{a}" title="d(a) := \abs{a}"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="13" src="https://math.fontein.de/formulae/EM67CoZde6CP8iAvo.3t8zO12j1er0hytBZGQw.svgz" alt="a \in \Z" title="a \in \Z"></span>.</li>
<li>Let <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="12" src="https://math.fontein.de/formulae/08bW5Zvy2ST6Ewwt6yOyAbfn7ZY0nrbV5GNE.Q.svgz" alt="K" title="K"></span> be a field and <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="15" src="https://math.fontein.de/formulae/Q.z47ttEWSdWJqiuzpDGtiLYMeMKUdBackmO6A.svgz" alt="q > 1" title="q > 1"></span> an arbitrary integer. Then, the polynomials <span class="inline-formula"><img class="img-inline-formula img-formula" width="78" height="18" src="https://math.fontein.de/formulae/ZoeE5tC9KluaODc0f.blM7gaE2Ufm_uuqCsF8w.svgz" alt="R := K[x]" title="R := K[x]"></span> form an Euclidean ring with <span class="inline-formula"><img class="img-inline-formula img-formula" width="104" height="19" src="https://math.fontein.de/formulae/ObOROBUo3bnWRrgxvuIM2NipNGiPJvz_WgrTVw.svgz" alt="d(f) := q^{\deg f}" title="d(f) := q^{\deg f}"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="18" src="https://math.fontein.de/formulae/HOLqIXdwZ6qAVqSw7hBMqGil.mFCJ6XhC8pklQ.svgz" alt="f \in K[x]" title="f \in K[x]"></span>.</li>
</ol>
<p>
A first, very remarkable property of Euclidean domains is that every ideal is principal; as a consequence of this, they possess a unique factorization of elements into products of primes. Moreover, since they are principal ideal domains, not only do greatest common divisors exist, but they can be written as a linear combination of the elements of whom they are the greatest common divisor! We will soon give a constructive proof for this, but before that note that this can be shown easily as follows: let <span class="inline-formula"><img class="img-inline-formula img-formula" width="111" height="16" src="https://math.fontein.de/formulae/FKNVz9xs_M21fzljBEkOx9Yue69LCNDfqLUNJg.svgz" alt="a_1, \dots, a_n \in R" title="a_1, \dots, a_n \in R"></span>; then the ideal <span class="inline-formula"><img class="img-inline-formula img-formula" width="89" height="18" src="https://math.fontein.de/formulae/OWRI1vA.eZpXoEnPRwEhxJE6LvEkTNlJWe0pbw.svgz" alt="(a_1, \dots, a_n)" title="(a_1, \dots, a_n)"></span> generated by them in <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/vYu2wcShMlDKJ.IrmXbb2no6ZOHI_2bIn_7ZWQ.svgz" alt="R" title="R"></span> is prinipcal, i.e. there exists an element <span class="inline-formula"><img class="img-inline-formula img-formula" width="45" height="13" src="https://math.fontein.de/formulae/lV.9KHtexGKybcPesmNYvfMhhCKQAbQsIJc3xg.svgz" alt="a \in R" title="a \in R"></span> such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="136" height="18" src="https://math.fontein.de/formulae/xxpRVLBLKsDb_J5Rl1j6OOJ8NFzD.eEzdRP_hQ.svgz" alt="(a_1, \dots, a_n) = (a)" title="(a_1, \dots, a_n) = (a)"></span>. Clearly, <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="18" src="https://math.fontein.de/formulae/Y.Bsa3f7ZUa7WtuBBNc8k91tln_u1r.SJqMMtw.svgz" alt="a_i \in (a)" title="a_i \in (a)"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="18" src="https://math.fontein.de/formulae/gfUdtqaqR3ymRKn1aiSZh4AOR64vjiqEGynDww.svgz" alt="a \mid a_i" title="a \mid a_i"></span>, i.e. <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="8" src="https://math.fontein.de/formulae/azRcBM3xT5fNJHpsWOTZlxYAFAmaA0iJVK1nog.svgz" alt="a" title="a"></span> is a common divisor of <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="11" src="https://math.fontein.de/formulae/YrTxO5lzuS0jStku17mnV4uCbFPELeWvt2o_pA.svgz" alt="a_1, \dots, a_n" title="a_1, \dots, a_n"></span>. Moreover, as <span class="inline-formula"><img class="img-inline-formula img-formula" width="120" height="18" src="https://math.fontein.de/formulae/fG2TWBqIhOSreO9hdqst2Sr7BHAmnvsKwTx6Iw.svgz" alt="a \in (a_1, \dots, a_n)" title="a \in (a_1, \dots, a_n)"></span>, there exist <span class="inline-formula"><img class="img-inline-formula img-formula" width="107" height="16" src="https://math.fontein.de/formulae/_CBt5ISJx3RBHJJbs3S__6R_ppvO1CgY_23DPg.svgz" alt="b_1, \dots, b_n \in R" title="b_1, \dots, b_n \in R"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="107" height="20" src="https://math.fontein.de/formulae/Cl13Oa6BfPH7_ibkVSdJNLviFGPYQvwl2YbU5g.svgz" alt="a = \sum_{i=1}^n a_i b_i" title="a = \sum_{i=1}^n a_i b_i"></span>. Hence, if <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="13" src="https://math.fontein.de/formulae/d.WmrMhHEHgcEM58I5DNHisHS2z1d6SAEtP9iQ.svgz" alt="a'" title="a'"></span> is another common divisor of <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="11" src="https://math.fontein.de/formulae/YrTxO5lzuS0jStku17mnV4uCbFPELeWvt2o_pA.svgz" alt="a_1, \dots, a_n" title="a_1, \dots, a_n"></span>, we have that <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="13" src="https://math.fontein.de/formulae/d.WmrMhHEHgcEM58I5DNHisHS2z1d6SAEtP9iQ.svgz" alt="a'" title="a'"></span> divides <span class="inline-formula"><img class="img-inline-formula img-formula" width="107" height="20" src="https://math.fontein.de/formulae/HFRqrUG3OVHEiEpF2drCbQHLWDX.1cvDDi.Fmw.svgz" alt="\sum_{i=1}^n a_i b_i = a" title="\sum_{i=1}^n a_i b_i = a"></span>; this shows that <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="8" src="https://math.fontein.de/formulae/azRcBM3xT5fNJHpsWOTZlxYAFAmaA0iJVK1nog.svgz" alt="a" title="a"></span> is a greatest common divisor of <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="11" src="https://math.fontein.de/formulae/YrTxO5lzuS0jStku17mnV4uCbFPELeWvt2o_pA.svgz" alt="a_1, \dots, a_n" title="a_1, \dots, a_n"></span>.
</p>
<p>
Now, let us present a constructive proof that every two elements of <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/vYu2wcShMlDKJ.IrmXbb2no6ZOHI_2bIn_7ZWQ.svgz" alt="R" title="R"></span> possess a greatest common divisor. The idea goes back to <a href="https://en.wikipedia.org/wiki/Euclid">Euclid</a>.
</p>
<div class="theorem-environment theorem-theorem-environment">
<div class="theorem-header theorem-theorem-header">
Theorem (The Euclidean Algorithm).
</div>
<div class="theorem-content theorem-theorem-content">
<p>
Let <span class="inline-formula"><img class="img-inline-formula img-formula" width="113" height="18" src="https://math.fontein.de/formulae/9SAKlUm4UqxfLIH5tbwFe_v8Oqcg1novaumT9g.svgz" alt="n, m \in R \setminus \{ 0 \}" title="n, m \in R \setminus \{ 0 \}"></span> be two non-zero elements. Define
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="215" height="64" src="https://math.fontein.de/formulae/bbwZYyG5Ll7tEdgKHjjnCkucppC4JTXGF8VnRA.svgz" alt="\Matrix{ a_{-1} & a_{-2} \\ x_{-1} & x_{-2} \\ y_{-1} & y_{-2} } := \Matrix{ m & n \\ 0 & 1 \\ 1 & 0 }." title="\Matrix{ a_{-1} & a_{-2} \\ x_{-1} & x_{-2} \\ y_{-1} & y_{-2} } := \Matrix{ m & n \\ 0 & 1 \\ 1 & 0 }.">
</div>
<p>
Then, inductively, define <span class="inline-formula"><img class="img-inline-formula img-formula" width="83" height="11" src="https://math.fontein.de/formulae/pvv_d0KpG4FAsgOMNEaBjUjV2.czL.1WHZE2sg.svgz" alt="a_i, x_i, y_i, q_i" title="a_i, x_i, y_i, q_i"></span> as follows, <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="13" src="https://math.fontein.de/formulae/nsBYnFhalS4zL.MWfsrOMkbWTLdznSQHsMKFYw.svgz" alt="i \in \N" title="i \in \N"></span>: Given the corresponding values for <span class="inline-formula"><img class="img-inline-formula img-formula" width="37" height="13" src="https://math.fontein.de/formulae/bxThAQVBWt18TGJLKS7fAdd_UYlLtnacXZ7PYQ.svgz" alt="i - 1" title="i - 1"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="37" height="13" src="https://math.fontein.de/formulae/3ysB62v93Lr9lG6NuZR8OkX9hTg4AN2AAV.idA.svgz" alt="i - 2" title="i - 2"></span>, there exist <span class="inline-formula"><img class="img-inline-formula img-formula" width="72" height="16" src="https://math.fontein.de/formulae/veH8W0bKF9SUX2Jh61VFG99E_01x1AIEAP8OiA.svgz" alt="a_i, q_i \in R" title="a_i, q_i \in R"></span> such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="141" height="14" src="https://math.fontein.de/formulae/ASK1TkV5jbQc7MRQGBrUBToqhR32fOV4UJr1hg.svgz" alt="a_{i-2} = q_i a_{i-1} + a_i" title="a_{i-2} = q_i a_{i-1} + a_i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="118" height="18" src="https://math.fontein.de/formulae/jQNE1k.2DyHXtH3Xd0lp9giCXUznizS9Fe.eng.svgz" alt="d(a_i) < d(a_{i-1})" title="d(a_i) < d(a_{i-1})"></span>. Moreover, set <span class="inline-formula"><img class="img-inline-formula img-formula" width="148" height="14" src="https://math.fontein.de/formulae/p0oDAO4Ltt11EfDCX01o27OcQX58uNE_egh.wQ.svgz" alt="x_i := x_{i-2} - q_i x_{i-1}" title="x_i := x_{i-2} - q_i x_{i-1}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="144" height="14" src="https://math.fontein.de/formulae/_YhyJMvkQlxTgctrxZfjw0XBThfoK.mnA5aOiQ.svgz" alt="y_i := y_{i-2} - q_i y_{i-1}" title="y_i := y_{i-2} - q_i y_{i-1}"></span>.
</p>
<p>
In case <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="14" src="https://math.fontein.de/formulae/4dmX4DYdycD12F5ag1J24PR2JjlUNaDbwbBzbw.svgz" alt="a_i = 0" title="a_i = 0"></span> for some <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>, set <span class="inline-formula"><img class="img-inline-formula img-formula" width="51" height="12" src="https://math.fontein.de/formulae/r6ojtOx1i6BL6J5p5ku7J1fIAjn.XNfCU8CDCw.svgz" alt="N := i" title="N := i"></span> and stop the process. Otherwise, set <span class="inline-formula"><img class="img-inline-formula img-formula" width="62" height="12" src="https://math.fontein.de/formulae/ORfoh_nlA5A1N5stwlxlVbyU8wcpVVoZDdPiBg.svgz" alt="N := \infty" title="N := \infty"></span>. Moreover, for <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="14" src="https://math.fontein.de/formulae/7mYteGmF4X2uIiiPBv8JOjPcFe1uEMAXaCKBgA.svgz" alt="i \ge -1" title="i \ge -1"></span> define
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="348" height="64" src="https://math.fontein.de/formulae/eytQTSxonwEMJDhb1y_zL0JMaOVOyuDw5ZOBGQ.svgz" alt="M_i := \Matrix{ a_i & a_{i-1} \\ x_i & x_{i-1} \\ y_i & y_{i-1} } \quad \text{and} \quad Q_i := \Matrix{ -q_i & 1 \\ 1 & 0 }." title="M_i := \Matrix{ a_i & a_{i-1} \\ x_i & x_{i-1} \\ y_i & y_{i-1} } \quad \text{and} \quad Q_i := \Matrix{ -q_i & 1 \\ 1 & 0 }.">
</div>
<p>
We then have the following properties:
</p>
<ol class="enum-level-1">
<li><span class="inline-formula"><img class="img-inline-formula img-formula" width="57" height="13" src="https://math.fontein.de/formulae/D_FNveyRyKmSuJ2FmOa1F0g5f4tXh9_hpGsqGQ.svgz" alt="N < \infty" title="N < \infty"></span>, i.e. the process terminates;</li>
<li>for <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="15" src="https://math.fontein.de/formulae/FhCxLOl8qZ37YiLGevo4cBxM_rtPUTLze91lTA.svgz" alt="i \le N" title="i \le N"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="117" height="14" src="https://math.fontein.de/formulae/TGv_HQfDR.bGOdweSCoWck728dylaVp7K41y9A.svgz" alt="a_i = x_i n + y_i m" title="a_i = x_i n + y_i m"></span>;</li>
<li>for <span class="inline-formula"><img class="img-inline-formula img-formula" width="78" height="15" src="https://math.fontein.de/formulae/.nl8p2wBjondpRBPrECuRZFehIQpEqAeMdvIAg.svgz" alt="0 \le i \le N" title="0 \le i \le N"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="108" height="16" src="https://math.fontein.de/formulae/2.elq7InnB3YMVx8HKc79aT6Gm33Bbr.dx1jQw.svgz" alt="M_i = M_{i-1} Q_i" title="M_i = M_{i-1} Q_i"></span>;</li>
<li>for <span class="inline-formula"><img class="img-inline-formula img-formula" width="92" height="15" src="https://math.fontein.de/formulae/m5otO86g.b0cADQq2zykOlftWgY54icfuGNh_g.svgz" alt="-2 \le i < N" title="-2 \le i < N"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="185" height="19" src="https://math.fontein.de/formulae/O5QFjejtZrcCFgR9lnBOWRL4fspeg47fUgQsLQ.svgz" alt="x_i y_{i+1} - x_{i+1} y_i = (-1)^i" title="x_i y_{i+1} - x_{i+1} y_i = (-1)^i"></span>;</li>
<li>we have that <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/Lbyxtyu3sD.mXErkNl6PSbFABmLPRbYAfJbbWw.svgz" alt="a_{N-1}" title="a_{N-1}"></span> is a greatest common divisor for <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span>;</li>
<li>we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="80" height="22" src="https://math.fontein.de/formulae/whJhLd6egGSrjg0pk8DZPa3whivKj4CywOyilw.svgz" alt="x_N \sim \frac{m}{a_{i-1}}" title="x_N \sim \frac{m}{a_{i-1}}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="79" height="22" src="https://math.fontein.de/formulae/obE4PEnqL3RPg7CWk9IZ.93ptuYNXfIxXYAktw.svgz" alt="y_N \sim \frac{n}{a_{i-1}}" title="y_N \sim \frac{n}{a_{i-1}}"></span>, where <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="6" src="https://math.fontein.de/formulae/7CCy3eLHRu9gOobKOrqS1H_e_JbMkBDj7nC25Q.svgz" alt="\sim" title="\sim"></span> means equal up to units (i.e. elements of <span class="inline-formula"><img class="img-inline-formula img-formula" width="22" height="12" src="https://math.fontein.de/formulae/5d9xiiszo5rKIQSEbohXb68zlB72VNkMZLUXHA.svgz" alt="R^*" title="R^*"></span>);</li>
<li>
<p>
the set of all <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="18" src="https://math.fontein.de/formulae/p1xOHJn1uc3KaP04NNve3_vm0Zr_NQ5jV8MqiQ.svgz" alt="(x, y)" title="(x, y)"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="132" height="14" src="https://math.fontein.de/formulae/fG8C8..5E1ScLcLFjShjX9LNFa1KyHxPa_Tz7Q.svgz" alt="a_{N-1} = x n + y m" title="a_{N-1} = x n + y m"></span> is given by
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="325" height="23" src="https://math.fontein.de/formulae/ilIoYL5ZSLt5KJjAAgzy2OtEWb9T7WYbq92mow.svgz" alt="\{ (x_{N-1} + \tfrac{m}{a_{N-1}} a, y_{N-1} - \tfrac{n}{a_{N-1}} a) \mid a \in R \};" title="\{ (x_{N-1} + \tfrac{m}{a_{N-1}} a, y_{N-1} - \tfrac{n}{a_{N-1}} a) \mid a \in R \};">
</div>
</li>
<li>for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/qc5XIH5o7W2booQ84E6XQLoB0b2m1BYpkO3g7A.svgz" alt="i = 1, \dots, N" title="i = 1, \dots, N"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="16" src="https://math.fontein.de/formulae/3hZzYqBaVWL4LTbyY1OvdqMOo4ZIffRkGmAe_w.svgz" alt="q_i \neq 0" title="q_i \neq 0"></span>; moreover, <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="15" src="https://math.fontein.de/formulae/gP7GbMxNJ5cDWu02PnXKW2XFgXNGbTFB2N0hzg.svgz" alt="q_0 = 0" title="q_0 = 0"></span> can only happen if <span class="inline-formula"><img class="img-inline-formula img-formula" width="96" height="18" src="https://math.fontein.de/formulae/WFLDlq.9n4TUF7t90JQmT.EApLAeT0uZ6DVcag.svgz" alt="d(n) < d(m)" title="d(n) < d(m)"></span>;</li>
<li>for <span class="inline-formula"><img class="img-inline-formula img-formula" width="108" height="16" src="https://math.fontein.de/formulae/YGN42SeEZcqoVoO57jRhKhwMkKdEkpHQ2VBDkA.svgz" alt="i = -1, \dots, N" title="i = -1, \dots, N"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="202" height="19" src="https://math.fontein.de/formulae/A2SIkVZ8EFoFr9GqtQeyXDNG5..DUaDZCp_d.g.svgz" alt="a_{i-1} x_i - x_{i-1} a_i = (-1)^i m" title="a_{i-1} x_i - x_{i-1} a_i = (-1)^i m"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="212" height="19" src="https://math.fontein.de/formulae/4l5a603yQSuYU7Sm_YW6pSzz0LB7hZVUP.C.Mw.svgz" alt="a_{i-1} y_i - y_{i-1} a_i = (-1)^{i-1} n" title="a_{i-1} y_i - y_{i-1} a_i = (-1)^{i-1} n"></span>.</li>
</ol>
</div>
</div>
<p>
This process of computing the <span class="inline-formula"><img class="img-inline-formula img-formula" width="62" height="11" src="https://math.fontein.de/formulae/7Ub7lMvDe2ZXj.i5.8J5CEV8uHGL2HSt9o6Fvg.svgz" alt="a_i, x_i, y_i" title="a_i, x_i, y_i"></span> is also known as the <a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">Extended Euclidean Algorithm</a> (EEA). It is used, for example, to find explicit solutions to the <a href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese Remainder Theorem</a>, as well as <a href="https://en.wikipedia.org/wiki/Modular_multiplicative_inverse">inverting elements</a> in <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="18" src="https://math.fontein.de/formulae/RiDtE2xonDg5Ezdr01F_j.hWCJiXDr5lm0_RTw.svgz" alt="\Z/n\Z" title="\Z/n\Z"></span> or <span class="inline-formula"><img class="img-inline-formula img-formula" width="69" height="18" src="https://math.fontein.de/formulae/PWKKT3rnRYZphrXZyBHnSb.F29xbekkTxPuliw.svgz" alt="K[x]/(f)" title="K[x]/(f)"></span>.
</p>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof.
</div>
<div class="theorem-content theorem-proof-content">
<ol class="enum-level-1">
<li>Note that <span class="inline-formula"><img class="img-inline-formula img-formula" width="118" height="18" src="https://math.fontein.de/formulae/jQNE1k.2DyHXtH3Xd0lp9giCXUznizS9Fe.eng.svgz" alt="d(a_i) < d(a_{i-1})" title="d(a_i) < d(a_{i-1})"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/7bOS.gW7YEc_Vl5o5rMonnTQYAeECKSB0p0pwQ.svgz" alt="i \ge 0" title="i \ge 0"></span>; therefore, as <span class="inline-formula"><img class="img-inline-formula img-formula" width="73" height="18" src="https://math.fontein.de/formulae/PbgkFJisP9qvzs5dxwurpggHNDVHVlMQ1DkutA.svgz" alt="d(a_i) \in \N" title="d(a_i) \in \N"></span>, we obtain a strictly decreasing sequence of natural numbers, which eventually has to stop. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="57" height="13" src="https://math.fontein.de/formulae/D_FNveyRyKmSuJ2FmOa1F0g5f4tXh9_hpGsqGQ.svgz" alt="N < \infty" title="N < \infty"></span>.</li>
<li>
<p>
We show this by <a href="https://en.wikipedia.org/wiki/Strong_induction#Complete_induction">strong induction</a> on <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>. First, for <span class="inline-formula"><img class="img-inline-formula img-formula" width="83" height="15" src="https://math.fontein.de/formulae/5ykxHOquTUOZB3K5VdVju.ZhHF2T32s1yVOs_Q.svgz" alt="i = -2, -1" title="i = -2, -1"></span>, the statement is true. Now assume it is true for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="38" height="15" src="https://math.fontein.de/formulae/WJJ1HvoR9_p3_uJWo1u6f7SBgcNc4RjQ4DbtBA.svgz" alt="j < i" title="j < i"></span>; using induction, we obtain
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="394" height="70" src="https://math.fontein.de/formulae/2Dcu9J6NCsGgh8rXjPX32oL7sJ7LofhvohXYmQ.svgz" alt="x_i n + y_i m ={} & (x_{i-2} - q_i x_{i-1}) n + (y_{i-2} - q_i y_{i-1}) m \\
& (x_{i-2} n + y_{i-2} m) - q_i (x_{i-1} n + y_{i-1} m) \\
{}={} & a_{i-2} - q_i a_{i-1} = a_i." title="x_i n + y_i m ={} & (x_{i-2} - q_i x_{i-1}) n + (y_{i-2} - q_i y_{i-1}) m \\
& (x_{i-2} n + y_{i-2} m) - q_i (x_{i-1} n + y_{i-1} m) \\
{}={} & a_{i-2} - q_i a_{i-1} = a_i.">
</div>
</li>
<li>This follows from <span class="inline-formula"><img class="img-inline-formula img-formula" width="141" height="14" src="https://math.fontein.de/formulae/BdbuK4raVi82x5s8efz9tNzmavqk8jxyDeT2dA.svgz" alt="a_i = a_{i-2} - a_{i-1} q_i" title="a_i = a_{i-2} - a_{i-1} q_i"></span> and the definitions of <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="10" src="https://math.fontein.de/formulae/7nfjEhdOyOz3m_veYQj2eKZvRfKLCKy4lcsijQ.svgz" alt="x_i" title="x_i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="11" src="https://math.fontein.de/formulae/0X6GQGIgJjCQdZ17cY.Uf9op.5NTFjjahnmPXA.svgz" alt="y_i" title="y_i"></span>.</li>
<li>
<p>
We show this by induction on <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>. For <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="13" src="https://math.fontein.de/formulae/GqBkUfmbvmZ4Y_eGKPsE.P0CwsPIZjmRD2_B9Q.svgz" alt="i = -2" title="i = -2"></span>, this is clearly true. Assume it is true for <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>; then
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="341" height="70" src="https://math.fontein.de/formulae/IXPRKp_dN7LyTsVDYpqdqhFoXJxhAu5XUVMDxQ.svgz" alt="& x_{i+1} y_{i+2} - x_{i+2} y_{i+1} \\
{}={} & x_{i+1} (y_i - q_{i+2} y_{i+1}) - (x_i - q_{i+2} x_{i+1}) y_{i+1} \\
{}={} & -(x_i y_{i+1} - x_{i+1} y_i) = -(-1)^i = (-1)^{i+1}." title="& x_{i+1} y_{i+2} - x_{i+2} y_{i+1} \\
{}={} & x_{i+1} (y_i - q_{i+2} y_{i+1}) - (x_i - q_{i+2} x_{i+1}) y_{i+1} \\
{}={} & -(x_i y_{i+1} - x_{i+1} y_i) = -(-1)^i = (-1)^{i+1}.">
</div>
</li>
<li>Let <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="8" src="https://math.fontein.de/formulae/azRcBM3xT5fNJHpsWOTZlxYAFAmaA0iJVK1nog.svgz" alt="a" title="a"></span> be a common divisor of <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span>. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="194" height="14" src="https://math.fontein.de/formulae/1ux7uTVzsi0XGBWrHpi.QQ6.vsYNeLb8OOsLDA.svgz" alt="a_{N-1} = x_{N-1} n + y_{N-1} m" title="a_{N-1} = x_{N-1} n + y_{N-1} m"></span>, we see that <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="8" src="https://math.fontein.de/formulae/azRcBM3xT5fNJHpsWOTZlxYAFAmaA0iJVK1nog.svgz" alt="a" title="a"></span> divides <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/Lbyxtyu3sD.mXErkNl6PSbFABmLPRbYAfJbbWw.svgz" alt="a_{N-1}" title="a_{N-1}"></span>. We now have to show that <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/Lbyxtyu3sD.mXErkNl6PSbFABmLPRbYAfJbbWw.svgz" alt="a_{N-1}" title="a_{N-1}"></span> divides both <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span>. We show that <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/Lbyxtyu3sD.mXErkNl6PSbFABmLPRbYAfJbbWw.svgz" alt="a_{N-1}" title="a_{N-1}"></span> divides <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="15" src="https://math.fontein.de/formulae/FhCxLOl8qZ37YiLGevo4cBxM_rtPUTLze91lTA.svgz" alt="i \le N" title="i \le N"></span>. It clearly divides <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/Lbyxtyu3sD.mXErkNl6PSbFABmLPRbYAfJbbWw.svgz" alt="a_{N-1}" title="a_{N-1}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="55" height="14" src="https://math.fontein.de/formulae/fBiPiwGBOqsmyqMUrD_nkhjbWZYz3GsAd93GtA.svgz" alt="a_N = 0" title="a_N = 0"></span>. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="159" height="14" src="https://math.fontein.de/formulae/zMuX1f_jqhFqUaH8dlQjjFJbCNxllwyAqsoIzA.svgz" alt="a_i = q_{i+2} a_{i+1} + a_{i+2}" title="a_i = q_{i+2} a_{i+1} + a_{i+2}"></span> is divisible by <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/Lbyxtyu3sD.mXErkNl6PSbFABmLPRbYAfJbbWw.svgz" alt="a_{N-1}" title="a_{N-1}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="240" height="16" src="https://math.fontein.de/formulae/uo0.1Zt6rB_0MWK4sfNJTC92xSJ6JgHVN4kwBg.svgz" alt="i = N-2, N-3, \dots, 0, -1, -2" title="i = N-2, N-3, \dots, 0, -1, -2"></span>; as <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="12" src="https://math.fontein.de/formulae/4C14uleBx_VqHXWqIVR_qTIO.9R4eu0eH.pVvw.svgz" alt="a_{-1} = m" title="a_{-1} = m"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="71" height="12" src="https://math.fontein.de/formulae/F5jrWUDOYMtjNlHgBZobOhlLEKhJhqVF2hVQxg.svgz" alt="a_{n-2} = n" title="a_{n-2} = n"></span>, the claim is proven.</li>
<li>We have <span class="inline-formula"><img class="img-inline-formula img-formula" width="172" height="15" src="https://math.fontein.de/formulae/8dB2kzVSpHYbk_ToZQ7p5q0aJBXzmKoxBAZY2A.svgz" alt="0 = a_N = x_N n + y_N m" title="0 = a_N = x_N n + y_N m"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="161" height="22" src="https://math.fontein.de/formulae/gG7Molw0gu2FBbI524pT4R1y0AnFuNxOD0SlBw.svgz" alt="x_N \frac{n}{a_{N-1}} = -y_N \frac{m}{a_{N-1}}" title="x_N \frac{n}{a_{N-1}} = -y_N \frac{m}{a_{N-1}}"></span>. Now <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="22" src="https://math.fontein.de/formulae/69icW790FgbTUCEReKJ9yHuWHDBBmX19xoq.IQ.svgz" alt="\frac{n}{a_{N-1}}" title="\frac{n}{a_{N-1}}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="22" src="https://math.fontein.de/formulae/rNI4whTtp9QAJkAx2NyocBqR5fPenXt4t7N63w.svgz" alt="\frac{m}{a_{N-1}}" title="\frac{m}{a_{N-1}}"></span> are coprime by (5), and <span class="inline-formula"><img class="img-inline-formula img-formula" width="24" height="10" src="https://math.fontein.de/formulae/wpzB4xacnShCepA1mVtz0NsS6lwVC9Y854mKeg.svgz" alt="x_N" title="x_N"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="22" height="11" src="https://math.fontein.de/formulae/XYs8Bap_ujcUJ_uKctd2LKeagRIrajn3msiHDg.svgz" alt="y_N" title="y_N"></span> are coprime by (4), whence we must have <span class="inline-formula"><img class="img-inline-formula img-formula" width="86" height="22" src="https://math.fontein.de/formulae/zoNneqh6FCezZ6aQxCvsSQHPCKYYnPAHYbEIGw.svgz" alt="x_N \sim \frac{m}{a_{N-1}}" title="x_N \sim \frac{m}{a_{N-1}}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="85" height="22" src="https://math.fontein.de/formulae/MfDp7eoWmqKJZhmJQ26uUAEbJ_fJ3_0lnWDDrA.svgz" alt="y_N \sim \frac{n}{a_{N-1}}" title="y_N \sim \frac{n}{a_{N-1}}"></span>.</li>
<li>Clearly, every element in the set is a solution of <span class="inline-formula"><img class="img-inline-formula img-formula" width="132" height="14" src="https://math.fontein.de/formulae/fG8C8..5E1ScLcLFjShjX9LNFa1KyHxPa_Tz7Q.svgz" alt="a_{N-1} = x n + y m" title="a_{N-1} = x n + y m"></span>, as <span class="inline-formula"><img class="img-inline-formula img-formula" width="186" height="23" src="https://math.fontein.de/formulae/1BNJm1bYjP9nLRwfd2Ip3p_obNhX5OugrylTXw.svgz" alt="\tfrac{m}{a_{N-1}} n + (-\tfrac{n}{a_{N-1}}) m = 0" title="\tfrac{m}{a_{N-1}} n + (-\tfrac{n}{a_{N-1}}) m = 0"></span>. Now let <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="18" src="https://math.fontein.de/formulae/p1xOHJn1uc3KaP04NNve3_vm0Zr_NQ5jV8MqiQ.svgz" alt="(x, y)" title="(x, y)"></span> satisfy <span class="inline-formula"><img class="img-inline-formula img-formula" width="132" height="14" src="https://math.fontein.de/formulae/fG8C8..5E1ScLcLFjShjX9LNFa1KyHxPa_Tz7Q.svgz" alt="a_{N-1} = x n + y m" title="a_{N-1} = x n + y m"></span>; then <span class="inline-formula"><img class="img-inline-formula img-formula" width="117" height="17" src="https://math.fontein.de/formulae/ezUAYqMPvOE3GEapbtfv7U804X9XP_ZfAjAG_g.svgz" alt="x' := x - x_{N-1}" title="x' := x - x_{N-1}"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="114" height="17" src="https://math.fontein.de/formulae/.eqYgbf8oHCP75GNtrXEllv.dq2S0xCUfucJWA.svgz" alt="y' := y + y_{N-1}" title="y' := y + y_{N-1}"></span> satisfy <span class="inline-formula"><img class="img-inline-formula img-formula" width="110" height="17" src="https://math.fontein.de/formulae/2M28iqozx1tokiZOU3IA9sL1frZSj9ZyNvXKAw.svgz" alt="x' n + y' m = 0" title="x' n + y' m = 0"></span>. Dividing by <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/Lbyxtyu3sD.mXErkNl6PSbFABmLPRbYAfJbbWw.svgz" alt="a_{N-1}" title="a_{N-1}"></span>, we get <span class="inline-formula"><img class="img-inline-formula img-formula" width="145" height="23" src="https://math.fontein.de/formulae/loGbCWzQlhRZHQaoTcKEGZkog9MUFKcr4c6BYQ.svgz" alt="x' \frac{n}{a_{N-1}} = -y' \frac{m}{a_{N-1}}" title="x' \frac{n}{a_{N-1}} = -y' \frac{m}{a_{N-1}}"></span>. By (5), we get that <span class="inline-formula"><img class="img-inline-formula img-formula" width="69" height="23" src="https://math.fontein.de/formulae/SWn1mInG08bLPMwsIJR1DElpqNYD7JW9.QA3uw.svgz" alt="\frac{m}{a_{N-1}} \mid x'" title="\frac{m}{a_{N-1}} \mid x'"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="23" src="https://math.fontein.de/formulae/_KvRoWEVybWO4.5WKxlA5KhpO5w6Sk7cytG6iQ.svgz" alt="\frac{n}{a_{N-1}} \mid y'" title="\frac{n}{a_{N-1}} \mid y'"></span>; write <span class="inline-formula"><img class="img-inline-formula img-formula" width="97" height="23" src="https://math.fontein.de/formulae/1sZ.9Br_PXVA24J1GSz.8n8kIKWxiWvYsnta2g.svgz" alt="x' = \frac{m}{a_{N-1}} x''" title="x' = \frac{m}{a_{N-1}} x''"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="95" height="23" src="https://math.fontein.de/formulae/oGcjU1tyvrBGj3vi6_p2DsEnnioOtCXfFKKgmA.svgz" alt="y' = \frac{n}{a_{N-1}} y''" title="y' = \frac{n}{a_{N-1}} y''"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="81" height="17" src="https://math.fontein.de/formulae/df2UpkesbVNJIbfLhOAQ3qP3AYJi8TkdqOc1KA.svgz" alt="x'', y'' \in R" title="x'', y'' \in R"></span>. This gives <span class="inline-formula"><img class="img-inline-formula img-formula" width="231" height="23" src="https://math.fontein.de/formulae/3vocCSDfZUwbCjZf8h3tNqBwcQRDJCd472Fm5w.svgz" alt="x'' \frac{m}{a_{N-1}} \frac{n}{a_{N-1}} = -y'' \frac{n}{a_{N-1}} \frac{m}{a_{N-1}}" title="x'' \frac{m}{a_{N-1}} \frac{n}{a_{N-1}} = -y'' \frac{n}{a_{N-1}} \frac{m}{a_{N-1}}"></span>, and cancelling shows <span class="inline-formula"><img class="img-inline-formula img-formula" width="75" height="17" src="https://math.fontein.de/formulae/fEnAi8MIyy9LDAHvrE8m4xsT8_VbbqPDby8XeA.svgz" alt="x'' = -y''" title="x'' = -y''"></span>; therefore, <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="18" src="https://math.fontein.de/formulae/p1xOHJn1uc3KaP04NNve3_vm0Zr_NQ5jV8MqiQ.svgz" alt="(x, y)" title="(x, y)"></span> lies in the set.</li>
<li>
<p>
We have <span class="inline-formula"><img class="img-inline-formula img-formula" width="105" height="14" src="https://math.fontein.de/formulae/1Hm7D3epHvRhS8X4hybVF8QHdyNnGOSCUZeoqw.svgz" alt="n = q_0 m + a_0" title="n = q_0 m + a_0"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="102" height="18" src="https://math.fontein.de/formulae/EYFmxc_1ChozBlbsCim3N9VtsZqW8tDhZYiATw.svgz" alt="d(a_0) < d(m)" title="d(a_0) < d(m)"></span>, whence we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="15" src="https://math.fontein.de/formulae/gP7GbMxNJ5cDWu02PnXKW2XFgXNGbTFB2N0hzg.svgz" alt="q_0 = 0" title="q_0 = 0"></span> if, and only if, <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="10" src="https://math.fontein.de/formulae/RBOWoPVzza6wq_oEeHz5I3CXS5dO9gZCxCvNIQ.svgz" alt="n = a_0" title="n = a_0"></span>. This can only happen if <span class="inline-formula"><img class="img-inline-formula img-formula" width="96" height="18" src="https://math.fontein.de/formulae/WFLDlq.9n4TUF7t90JQmT.EApLAeT0uZ6DVcag.svgz" alt="d(n) < d(m)" title="d(n) < d(m)"></span>.
</p>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/i5mcvyDpWMGwXT1XJyBr5nEbjZwc3hX_xbFIfA.svgz" alt="i > 0" title="i > 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="198" height="18" src="https://math.fontein.de/formulae/mBbR1kTMEGqzBLIufvzGhFbKE2EZPK8QvjKDUQ.svgz" alt="d(a_i) < d(a_{i-1}) < d(a_{i-2})" title="d(a_i) < d(a_{i-1}) < d(a_{i-2})"></span>, whereas <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="15" src="https://math.fontein.de/formulae/GWWCfizmegTHCqmEN_HtY064MLwF8FCM4XTFuw.svgz" alt="q_i = 0" title="q_i = 0"></span> would imply <span class="inline-formula"><img class="img-inline-formula img-formula" width="72" height="12" src="https://math.fontein.de/formulae/_npZLmCYZIq.a.ay5GmqpjCwizMQgtunSIdcqw.svgz" alt="a_i = a_{i-2}" title="a_i = a_{i-2}"></span>.
</p>
</li>
<li>
<p>
We have
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="297" height="102" src="https://math.fontein.de/formulae/yJb73VoCMKTTcNxFvzZttXmHweADHTiYEKv6LA.svgz" alt="a_{i-1} x_i ={} & x_{i-1} x_i n + y_{i-1} x_i m \\
{}={} & x_{i-1} x_i n + (y_i x_{i-1} + (-1)^i) m \\
{}={} & x_{i-1} (x_i n + y_i m) + (-1)^i m \\
{}={} & x_{i-1} a_i + (-1)^i m" title="a_{i-1} x_i ={} & x_{i-1} x_i n + y_{i-1} x_i m \\
{}={} & x_{i-1} x_i n + (y_i x_{i-1} + (-1)^i) m \\
{}={} & x_{i-1} (x_i n + y_i m) + (-1)^i m \\
{}={} & x_{i-1} a_i + (-1)^i m">
</div>
<p>
and
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="311" height="102" src="https://math.fontein.de/formulae/_iwPjC42d_orWXKWr_efrRseZUriWEvMxs4WFQ.svgz" alt="a_{i-1} y_i ={} & x_{i-1} y_i n + y_{i-1} y_i m \\
{}={} & (y_{i-1} x_i + (-1)^{i-1}) n + y_{i-1} y_i m \\
{}={} & y_{i-1} (x_i n + y_i m) + (-1)^{i-1} n \\
{}={} & y_{i-1} a_i + (-1)^{i-1} n." title="a_{i-1} y_i ={} & x_{i-1} y_i n + y_{i-1} y_i m \\
{}={} & (y_{i-1} x_i + (-1)^{i-1}) n + y_{i-1} y_i m \\
{}={} & y_{i-1} (x_i n + y_i m) + (-1)^{i-1} n \\
{}={} & y_{i-1} a_i + (-1)^{i-1} n.">
</div>
</li>
</ol>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
<p>
We note two special properties of Euclidean division for <span class="inline-formula"><img class="img-inline-formula img-formula" width="12" height="12" src="https://math.fontein.de/formulae/wHyKSgMZTFrtdvMomD9SLs8Z27XS7B.vR28n6w.svgz" alt="\Z" title="\Z"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="36" height="18" src="https://math.fontein.de/formulae/BNKKIdTL7sjVxVBqSpcm.WB4SoqacHkAv3dKtg.svgz" alt="K[x]" title="K[x]"></span>:
</p>
<ol class="enum-level-1">
<li>In case of <span class="inline-formula"><img class="img-inline-formula img-formula" width="49" height="12" src="https://math.fontein.de/formulae/gPtnrnCRKvU6tn.YsAQGByPRdRPTop12CSmtnA.svgz" alt="R = \Z" title="R = \Z"></span>, one can make <span class="inline-formula"><img class="img-inline-formula img-formula" width="8" height="8" src="https://math.fontein.de/formulae/9PDR_uZ5xxt4l_bI_FVKMXrwFl94B6.ue5eEfg.svgz" alt="r" title="r"></span> unique by specifying <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="14" src="https://math.fontein.de/formulae/b1mUQ5U8EhEDnW14eAmqNTNdPyJyaoXcWlkPxg.svgz" alt="r \le 0" title="r \le 0"></span> or <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="14" src="https://math.fontein.de/formulae/IFri7YXLCx3m7bveB_n7Jjg0sdXe0NrLSp486w.svgz" alt="r \ge 0" title="r \ge 0"></span>. I.e., for every <span class="inline-formula"><img class="img-inline-formula img-formula" width="58" height="16" src="https://math.fontein.de/formulae/wmojGlvr6p4LGKVOrM0Klkp7w.gR2T8hQJyW7A.svgz" alt="a, b \in \Z" title="a, b \in \Z"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="40" height="16" src="https://math.fontein.de/formulae/vQEhWqcf0URCoLapqQSLHWiUU_Bwf0OJZC7vMg.svgz" alt="b \neq 0" title="b \neq 0"></span> there exists unique elements <span class="inline-formula"><img class="img-inline-formula img-formula" width="100" height="17" src="https://math.fontein.de/formulae/rBq9LnO5E_ZxW7QAnJvlr9GfemoU1uDOs66h7A.svgz" alt="q, r, q', r' \in \Z" title="q, r, q', r' \in \Z"></span> such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="159" height="17" src="https://math.fontein.de/formulae/vuyc4RAS3YH7fMi6hOHc2rM7sdYAjTKe7EerPA.svgz" alt="a = q b + r = q' b + r'" title="a = q b + r = q' b + r'"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="141" height="18" src="https://math.fontein.de/formulae/Uy07QIBR3akNIDW16i5XuUMYUrWmnTH8qkhusg.svgz" alt="-\abs{b} < r' \le r < \abs{b}" title="-\abs{b} < r' \le r < \abs{b}"></span>. Note, that in case <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="17" src="https://math.fontein.de/formulae/Z4hZLgyQi0Kfn2ZjUf26cq2CNnkxSNuN0xoQFw.svgz" alt="r' \neq r" title="r' \neq r"></span> we have that <em>either</em> <span class="inline-formula"><img class="img-inline-formula img-formula" width="92" height="18" src="https://math.fontein.de/formulae/9DBDVQDyytcGZY2.uHDLktuYovrlahgRYnm_5A.svgz" alt="\abs{a - r} \le \abs{a}" title="\abs{a - r} \le \abs{a}"></span> <em>or</em> <span class="inline-formula"><img class="img-inline-formula img-formula" width="97" height="18" src="https://math.fontein.de/formulae/14PQS9VGUSWELYC4OmXADe2j9hBnStSdHAk28g.svgz" alt="\abs{a - r'} \le \abs{a}" title="\abs{a - r'} \le \abs{a}"></span>.</li>
<li>In case of <span class="inline-formula"><img class="img-inline-formula img-formula" width="73" height="18" src="https://math.fontein.de/formulae/r66UyyBdKal98xBTZx1VaKQbur9I06wby6eQ7g.svgz" alt="R = K[x]" title="R = K[x]"></span>, the polynomials <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/TS.AXB89SbmV6ikqkLFw.pZs0NgSF4Ag7MxPOg.svgz" alt="q" title="q"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="8" height="8" src="https://math.fontein.de/formulae/9PDR_uZ5xxt4l_bI_FVKMXrwFl94B6.ue5eEfg.svgz" alt="r" title="r"></span> are unique and satisfy <span class="inline-formula"><img class="img-inline-formula img-formula" width="143" height="18" src="https://math.fontein.de/formulae/PtRoQYJ46MRJEQbZcwo62eR9uUV1nzA0946TBg.svgz" alt="\deg (a - r) \le \deg a" title="\deg (a - r) \le \deg a"></span>: if <span class="inline-formula"><img class="img-inline-formula img-formula" width="159" height="17" src="https://math.fontein.de/formulae/vuyc4RAS3YH7fMi6hOHc2rM7sdYAjTKe7EerPA.svgz" alt="a = q b + r = q' b + r'" title="a = q b + r = q' b + r'"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="18" src="https://math.fontein.de/formulae/192YVpI_zQbNTYJq8mi6RoR.m6tOXxJ8NeyEtQ.svgz" alt="q, q', r, r' \in K[x]" title="q, q', r, r' \in K[x]"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="149" height="17" src="https://math.fontein.de/formulae/OdgFaJWUS4V2BzYf1f.HdfQBCJlOcMQ6wV2bwA.svgz" alt="\deg r, \deg r' < \deg b" title="\deg r, \deg r' < \deg b"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="132" height="18" src="https://math.fontein.de/formulae/VKaV4zaNWlrGVMU75gABL4AgS.dcXYgVf38HVQ.svgz" alt="r - r' = b (q' - q)" title="r - r' = b (q' - q)"></span>. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="145" height="18" src="https://math.fontein.de/formulae/2GuJHM2CNXaPaB8YQo8yGZsfLgQVSTNTZdkiTw.svgz" alt="\deg(r - r') < \deg b" title="\deg(r - r') < \deg b"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="273" height="18" src="https://math.fontein.de/formulae/PA5q4YfvMfV8EPj.NMk49rhezVf3uu.0ZY9Vog.svgz" alt="\deg (b (q' - q)) = \deg b + \deg (q' - q)" title="\deg (b (q' - q)) = \deg b + \deg (q' - q)"></span>, we must have <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="17" src="https://math.fontein.de/formulae/ItbvszUkL9dF0T2ZnMkgM1nYjhKSykCQZ2MPAg.svgz" alt="q' - q = 0" title="q' - q = 0"></span>, hence also <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="15" src="https://math.fontein.de/formulae/HonizoRKdbFuaJdmiv4GY..qXT4NZf5GL7cDdw.svgz" alt="r - r' = 0" title="r - r' = 0"></span>. Now if <span class="inline-formula"><img class="img-inline-formula img-formula" width="100" height="16" src="https://math.fontein.de/formulae/PTJ85USv986dCXi2QQBiADbhzrtD3i9fJ6uXZw.svgz" alt="\deg a < \deg b" title="\deg a < \deg b"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="8" src="https://math.fontein.de/formulae/q.lSWgOK10_UP8JjlQcUzxsqfnVCHJUwtGFDMw.svgz" alt="r = a" title="r = a"></span>; otherwise, <span class="inline-formula"><img class="img-inline-formula img-formula" width="162" height="16" src="https://math.fontein.de/formulae/T6VXm6PBu3PvhUA8xkyA0tT6XudQtY5Ylos3Tw.svgz" alt="\deg r < \deg b \le \deg a" title="\deg r < \deg b \le \deg a"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="143" height="18" src="https://math.fontein.de/formulae/CK6AmUOfoj4S2gAw_zOzASVenkIk_2c9pG6f_w.svgz" alt="\deg(a - r) = \deg a" title="\deg(a - r) = \deg a"></span>.</li>
</ol>
<p>
Hence, in both cases, for every <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="16" src="https://math.fontein.de/formulae/BKHzTmQHrr.6UYl.goLGl6zjuc.8tW3k6zxpYA.svgz" alt="a, b \in R" title="a, b \in R"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="40" height="16" src="https://math.fontein.de/formulae/vQEhWqcf0URCoLapqQSLHWiUU_Bwf0OJZC7vMg.svgz" alt="b \neq 0" title="b \neq 0"></span>, there exist <em>unique</em> <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="16" src="https://math.fontein.de/formulae/s9cA9.ahzSqmWkfb3ASb5eBb3tgPPBAYb1XHvQ.svgz" alt="q, r \in R" title="q, r \in R"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="79" height="16" src="https://math.fontein.de/formulae/Iz6QryYjEkFoZLQqQAcSTFq4Ry.7N5dcFbaPbA.svgz" alt="a = q b + r" title="a = q b + r"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="86" height="18" src="https://math.fontein.de/formulae/VV4.jOEnP0Z5sUZ237sb1s6rITySbjCxLaw1qw.svgz" alt="d(r) < d(b)" title="d(r) < d(b)"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="181" height="18" src="https://math.fontein.de/formulae/hE2Bmexvk7QzBvL271bvisziPGQvB9GytLoiGQ.svgz" alt="d(a - r) = d(q b) \le d(a)" title="d(a - r) = d(q b) \le d(a)"></span>.
</p>
<p>
In the following, we prove several properties for the Extended Euclidean Algorithm for both cases. We begin with the integer case.
</p>
<div class="theorem-environment theorem-proposition-environment">
<div class="theorem-header theorem-proposition-header">
Proposition.
</div>
<div class="theorem-content theorem-proposition-content">
<p>
Assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="67" height="16" src="https://math.fontein.de/formulae/a0xq8Dv9Q3Rk3Gfp.9ZqJ27kXtS6iuyzkn9jdQ.svgz" alt="n, m \neq 0" title="n, m \neq 0"></span>, that <span class="inline-formula"><img class="img-inline-formula img-formula" width="49" height="12" src="https://math.fontein.de/formulae/gPtnrnCRKvU6tn.YsAQGByPRdRPTop12CSmtnA.svgz" alt="R = \Z" title="R = \Z"></span> and that <span class="inline-formula"><img class="img-inline-formula img-formula" width="74" height="18" src="https://math.fontein.de/formulae/JyWTOzqZOxYOQtpoUG0aaYdScFa.LzN8FUE98w.svgz" alt="d(z) = \abs{z}" title="d(z) = \abs{z}"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="42" height="13" src="https://math.fontein.de/formulae/XtGZOZkBTPhMI_D4hlZYkj88d2DK4hHcnUBKpQ.svgz" alt="z \in \Z" title="z \in \Z"></span>. Moreover, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="11" src="https://math.fontein.de/formulae/9Zv2E.GBERyjqgYtQWmv6ZHV8XYFW13z69al9Q.svgz" alt="q_i" title="q_i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> are chosen as above, i.e. such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="147" height="18" src="https://math.fontein.de/formulae/UeYH.llAFJGWrcq.lMg4Dd7u6HZg79vVzLy0QQ.svgz" alt="\abs{a_{i-2} - a_i} \le \abs{a_{i-2}}" title="\abs{a_{i-2} - a_i} \le \abs{a_{i-2}}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/v7audDREWLvwbLnxGi1y1g0YI9wPKye.BRA68Q.svgz" alt="i = 0, \dots, N" title="i = 0, \dots, N"></span>. Then:
</p>
<ol class="enum-level-1">
<li>we have that <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="33" height="12" src="https://math.fontein.de/formulae/Svk6ktiqLfKfRt.XxNK0yH7n5zGcMBDBhZPmjQ.svgz" alt="a_{i-2}" title="a_{i-2}"></span> have the same sign for <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="16" src="https://math.fontein.de/formulae/kaEFvlmNQdmd9IsSHKhUhUjE6DcUof1myy1uyg.svgz" alt="i = 0, \dots, N - 1" title="i = 0, \dots, N - 1"></span>;</li>
<li>we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="15" src="https://math.fontein.de/formulae/LmuXLYsBXAHJCkhIZTBCwLYqlPTfbxkd7cL1lQ.svgz" alt="q_i \ge 0" title="q_i \ge 0"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span> if <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span> have the same sign, and <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="15" src="https://math.fontein.de/formulae/2x07J7u7EdgajAjxOfHk.bZM7BK42IoS5S.GIA.svgz" alt="q_i \le 0" title="q_i \le 0"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span> if <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span> have different signs.</li>
<li>if <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span> have the same signs, <span class="inline-formula"><img class="img-inline-formula img-formula" width="91" height="19" src="https://math.fontein.de/formulae/XFyGKH4wLbHrbqS360SUoTc0Vj6.zCQL1atZug.svgz" alt="(-1)^i x_i \ge 0" title="(-1)^i x_i \ge 0"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="107" height="19" src="https://math.fontein.de/formulae/aQNdtgOmiZBoXVQsdCSe.cNsuKBKSlgApzBnjA.svgz" alt="(-1)^{i+1} y_i \ge 0" title="(-1)^{i+1} y_i \ge 0"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="108" height="16" src="https://math.fontein.de/formulae/mhuvhXZcVTVPvReNTOeLwsjfQHpi_e962JAn7w.svgz" alt="i = -2, \dots, N" title="i = -2, \dots, N"></span>; if <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span> have different signs, <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="14" src="https://math.fontein.de/formulae/xC5Io7bExAaO7JCeywT5l11rr3wqSbAW5GIcHQ.svgz" alt="x_i \ge 0" title="x_i \ge 0"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="15" src="https://math.fontein.de/formulae/1.luKKDVNYiPLRcglhY1IJ1xAYy2drFqcekaWg.svgz" alt="y_i \ge 0" title="y_i \ge 0"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="108" height="16" src="https://math.fontein.de/formulae/mhuvhXZcVTVPvReNTOeLwsjfQHpi_e962JAn7w.svgz" alt="i = -2, \dots, N" title="i = -2, \dots, N"></span>;</li>
<li>we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="322" height="18" src="https://math.fontein.de/formulae/.MdDiIc_xtFKJL7o.Eo8qPnYXKjH1YGDWS8hcw.svgz" alt="\abs{x_i} = \abs{q_i x_{i-1}} + \abs{x_{i-2}} > \abs{q_i x_{i-1}} \ge \abs{x_{i-1}}" title="\abs{x_i} = \abs{q_i x_{i-1}} + \abs{x_{i-2}} > \abs{q_i x_{i-1}} \ge \abs{x_{i-1}}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/v7audDREWLvwbLnxGi1y1g0YI9wPKye.BRA68Q.svgz" alt="i = 0, \dots, N" title="i = 0, \dots, N"></span>, and <span class="inline-formula"><img class="img-inline-formula img-formula" width="315" height="18" src="https://math.fontein.de/formulae/PwogSe5VisowGOnrGd52sNNji0UDjh7jnEz3Mw.svgz" alt="\abs{y_i} = \abs{q_i y_{i-1}} + \abs{y_{i-2}} > \abs{q_i y_{i-1}} \ge \abs{y_{i-1}}" title="\abs{y_i} = \abs{q_i y_{i-1}} + \abs{y_{i-2}} > \abs{q_i y_{i-1}} \ge \abs{y_{i-1}}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/qc5XIH5o7W2booQ84E6XQLoB0b2m1BYpkO3g7A.svgz" alt="i = 1, \dots, N" title="i = 1, \dots, N"></span>;</li>
<li>if <span class="inline-formula"><img class="img-inline-formula img-formula" width="140" height="18" src="https://math.fontein.de/formulae/e1jQ0KiPOSUqr4hPfjgvpXcHmXIrxXUpF8oa4A.svgz" alt="i, j \in \{ -2, \dots, N \}" title="i, j \in \{ -2, \dots, N \}"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="108" height="18" src="https://math.fontein.de/formulae/9ON1a3uJSuir6_Q0zZRlK6JSLw8WOOhZ4Pcadg.svgz" alt="i \not\equiv j \pmod{2}" title="i \not\equiv j \pmod{2}"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="109" height="21" src="https://math.fontein.de/formulae/FMB8bGs8i9V.wWsTOb9Fl.NNv4sQlcU5aMHqcw.svgz" alt="(-1)^j \frac{a_i x_j}{m} \ge 0" title="(-1)^j \frac{a_i x_j}{m} \ge 0"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="106" height="21" src="https://math.fontein.de/formulae/0WTjQMC_Ylay1HzILcCVqBOfEjSM4_2L6rnpEA.svgz" alt="(-1)^i \frac{a_i y_j}{n} \ge 0" title="(-1)^i \frac{a_i y_j}{n} \ge 0"></span>;</li>
<li>we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="91" height="27" src="https://math.fontein.de/formulae/K2Hxa3qB3Nu6qZDV.uqDuSgETWnBoWaJKDf2Iw.svgz" alt="\abs{x_i} \le \frac{\abs{m}}{\abs{a_{i-1}}}" title="\abs{x_i} \le \frac{\abs{m}}{\abs{a_{i-1}}}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="103" height="27" src="https://math.fontein.de/formulae/fCJLSeEWRObNz9_dvaJMRD5oEWRAYDT5cjxc5w.svgz" alt="d(y_i) \le \frac{\abs{n}}{\abs{a_{i-1}}}" title="d(y_i) \le \frac{\abs{n}}{\abs{a_{i-1}}}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="16" src="https://math.fontein.de/formulae/_DQMbAZ3dEtZ9PnpvBNT4KG0SnQg4YQGXa2Hsw.svgz" alt="i = -1, 0, \dots, N" title="i = -1, 0, \dots, N"></span>;</li>
<li>for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/qc5XIH5o7W2booQ84E6XQLoB0b2m1BYpkO3g7A.svgz" alt="i = 1, \dots, N" title="i = 1, \dots, N"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="103" height="21" src="https://math.fontein.de/formulae/zznaFOgayYYbSvgi0rcDcAqYVX_NLTKfyY5aSw.svgz" alt="\abs{a_i} < \frac{1}{2} \abs{a_{i-2}}" title="\abs{a_i} < \frac{1}{2} \abs{a_{i-2}}"></span>; therefore, <span class="inline-formula"><img class="img-inline-formula img-formula" width="102" height="19" src="https://math.fontein.de/formulae/xwR78EKEdm6R9HxcydiDmffD1Z5098IT8y.D7w.svgz" alt="\abs{a_{2i}} \le 2^{-i} \abs{n}" title="\abs{a_{2i}} \le 2^{-i} \abs{n}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="19" src="https://math.fontein.de/formulae/I3hS0ZCqjiWdP.KPdvXpbTUPAuYKWpwsGrFPiA.svgz" alt="\abs{a_{2i+1}} \le 2^{-i} \abs{m}" title="\abs{a_{2i+1}} \le 2^{-i} \abs{m}"></span>.</li>
</ol>
</div>
</div>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof.
</div>
<div class="theorem-content theorem-proof-content">
<ol class="enum-level-1">
<li>By construction, <span class="inline-formula"><img class="img-inline-formula img-formula" width="141" height="14" src="https://math.fontein.de/formulae/ASK1TkV5jbQc7MRQGBrUBToqhR32fOV4UJr1hg.svgz" alt="a_{i-2} = q_i a_{i-1} + a_i" title="a_{i-2} = q_i a_{i-1} + a_i"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="92" height="18" src="https://math.fontein.de/formulae/hXVH25KkSX.5p2snrXEouEpL3_on1gnP88RHgw.svgz" alt="\abs{a_i} < \abs{a_{i-1}}" title="\abs{a_i} < \abs{a_{i-1}}"></span>. As we required <span class="inline-formula"><img class="img-inline-formula img-formula" width="173" height="18" src="https://math.fontein.de/formulae/t7tu5AEly3WzACWF1tTU41n82Bs45mdhvw5lYg.svgz" alt="d(a_{i-2} - a_i) \le d(a_{i-2})" title="d(a_{i-2} - a_i) \le d(a_{i-2})"></span>, we must have that <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="33" height="12" src="https://math.fontein.de/formulae/Svk6ktiqLfKfRt.XxNK0yH7n5zGcMBDBhZPmjQ.svgz" alt="a_{i-2}" title="a_{i-2}"></span> have the same sign if <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="16" src="https://math.fontein.de/formulae/yvNm_FjZrEgGcTZc3aGwd68el70MiTIqgi9QbQ.svgz" alt="a_i \neq 0" title="a_i \neq 0"></span>.</li>
<li>Note that by our choice, <span class="inline-formula"><img class="img-inline-formula img-formula" width="92" height="18" src="https://math.fontein.de/formulae/9e._.Omd8qXwZODxJuu4zWLr3K9MdXt2eO9r.A.svgz" alt="\abs{a_i} \le \abs{a_{i-2}}" title="\abs{a_i} \le \abs{a_{i-2}}"></span> and both are either <span class="inline-formula"><img class="img-inline-formula img-formula" width="28" height="14" src="https://math.fontein.de/formulae/DB16W2SgGRiMLMS4CPZOIjZxGr.vCZ0gaf7vww.svgz" alt="\le 0" title="\le 0"></span> or <span class="inline-formula"><img class="img-inline-formula img-formula" width="28" height="14" src="https://math.fontein.de/formulae/GHb4KZuBep1FzeoJBOXP1vfJxnaPOQavfXGtpg.svgz" alt="\ge 0" title="\ge 0"></span>, i.e. <span class="inline-formula"><img class="img-inline-formula img-formula" width="70" height="14" src="https://math.fontein.de/formulae/XwXeHo5H_I2pRjAdfOvZeCZ1mdMrjLVA3N6C2g.svgz" alt="a_i - a_{i-2}" title="a_i - a_{i-2}"></span> has the same sign as <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span>. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="141" height="14" src="https://math.fontein.de/formulae/g1wxKq..v7D.RWr.YUMLMFLHAeH_PJnG_BVC_g.svgz" alt="a_i - a_{i-2} = q_i a_{i-1}" title="a_i - a_{i-2} = q_i a_{i-1}"></span>, the claim follows.</li>
<li>
<p>
If <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span> have the same sign, <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="15" src="https://math.fontein.de/formulae/LmuXLYsBXAHJCkhIZTBCwLYqlPTfbxkd7cL1lQ.svgz" alt="q_i \ge 0" title="q_i \ge 0"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>. We show the claim by strong induction on <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>. For <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="13" src="https://math.fontein.de/formulae/GqBkUfmbvmZ4Y_eGKPsE.P0CwsPIZjmRD2_B9Q.svgz" alt="i = -2" title="i = -2"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="13" src="https://math.fontein.de/formulae/TpV8XX6cWvgLDrfsRgJ2NmMpZN1oHih_X3pYXw.svgz" alt="i = -1" title="i = -1"></span>, the claim follows from the definition. For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/7bOS.gW7YEc_Vl5o5rMonnTQYAeECKSB0p0pwQ.svgz" alt="i \ge 0" title="i \ge 0"></span>,
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="311" height="49" src="https://math.fontein.de/formulae/MNrBOC3LcInECjBDJQtjZvLh48Sc2knLZrITUg.svgz" alt="(-1)^i x_i ={} & (-1)^i x_{i-2} - (-1)^i q_i x_{i-1} \\
{}={} & (-1)^{i-2} x_{i-2} + q_i (-1)^{i-1} x_{i-1};" title="(-1)^i x_i ={} & (-1)^i x_{i-2} - (-1)^i q_i x_{i-1} \\
{}={} & (-1)^{i-2} x_{i-2} + q_i (-1)^{i-1} x_{i-1};">
</div>
<p>
as all terms on the right hand side are <span class="inline-formula"><img class="img-inline-formula img-formula" width="28" height="14" src="https://math.fontein.de/formulae/GHb4KZuBep1FzeoJBOXP1vfJxnaPOQavfXGtpg.svgz" alt="\ge 0" title="\ge 0"></span>, we get <span class="inline-formula"><img class="img-inline-formula img-formula" width="91" height="19" src="https://math.fontein.de/formulae/XFyGKH4wLbHrbqS360SUoTc0Vj6.zCQL1atZug.svgz" alt="(-1)^i x_i \ge 0" title="(-1)^i x_i \ge 0"></span>. The same argument shows that <span class="inline-formula"><img class="img-inline-formula img-formula" width="107" height="19" src="https://math.fontein.de/formulae/aQNdtgOmiZBoXVQsdCSe.cNsuKBKSlgApzBnjA.svgz" alt="(-1)^{i+1} y_i \ge 0" title="(-1)^{i+1} y_i \ge 0"></span>.
</p>
<p>
If <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="8" src="https://math.fontein.de/formulae/Ln3FmQu8Rxbv_tjKkeMJZrLhqAFAWD18KRPi9w.svgz" alt="m" title="m"></span> have different signs, <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="15" src="https://math.fontein.de/formulae/2x07J7u7EdgajAjxOfHk.bZM7BK42IoS5S.GIA.svgz" alt="q_i \le 0" title="q_i \le 0"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>. Again, for <span class="inline-formula"><img class="img-inline-formula img-formula" width="83" height="15" src="https://math.fontein.de/formulae/5ykxHOquTUOZB3K5VdVju.ZhHF2T32s1yVOs_Q.svgz" alt="i = -2, -1" title="i = -2, -1"></span>, the claim is clear. If <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/7bOS.gW7YEc_Vl5o5rMonnTQYAeECKSB0p0pwQ.svgz" alt="i \ge 0" title="i \ge 0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="331" height="18" src="https://math.fontein.de/formulae/.yQLwY9PokuSo4uE.2VIsLXBYKOVNE_L5OZ2AA.svgz" alt="x_i = x_{i-2} - q_i x_{i-1} = x_{i-2} + (-q_i) x_{i-1} \ge 0" title="x_i = x_{i-2} - q_i x_{i-1} = x_{i-2} + (-q_i) x_{i-1} \ge 0"></span> by strong induction, and similarly <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="15" src="https://math.fontein.de/formulae/1.luKKDVNYiPLRcglhY1IJ1xAYy2drFqcekaWg.svgz" alt="y_i \ge 0" title="y_i \ge 0"></span>.
</p>
</li>
<li>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/AP.hyMhQKFwhJ_dXBRqSnJYvMRd9RDeJaL2HKg.svgz" alt="i = 0" title="i = 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="62" height="16" src="https://math.fontein.de/formulae/.1fDgxBWVNn_olWEDLuf1h5jaQkkTMIjLrtMMQ.svgz" alt="x_{-1} = 0" title="x_{-1} = 0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="51" height="14" src="https://math.fontein.de/formulae/MEJm6uvT5cjZ0tq0rdtdUrEQFuP_I9sI_gH6dg.svgz" alt="x_0 = 1" title="x_0 = 1"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="201" height="18" src="https://math.fontein.de/formulae/FAePHOX4qug5P4Ppi86Dly5C9Lbh0.EHvpxMeA.svgz" alt="\abs{x_0} > 0 = \abs{q_0 x_{-1}} = \abs{x_{-1}}" title="\abs{x_0} > 0 = \abs{q_0 x_{-1}} = \abs{x_{-1}}"></span>. For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/_Z0Zet3FGKXwxkUDNgJLTR8s1GiVWihuREJy0w.svgz" alt="i = 1" title="i = 1"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="70" height="14" src="https://math.fontein.de/formulae/RrpqeHOyTMDIBDyzQ0oCo6yZ8PBYYTXatstKQA.svgz" alt="y_0 = -q_0" title="y_0 = -q_0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="102" height="15" src="https://math.fontein.de/formulae/lUr6.dxMhGhaS4354d0ECWeNqq1lCs1GF9h1Rw.svgz" alt="y_1 = 1 + q_0 q_1" title="y_1 = 1 + q_0 q_1"></span>; as <span class="inline-formula"><img class="img-inline-formula img-formula" width="64" height="15" src="https://math.fontein.de/formulae/h.34bT8Unr63kswy7WeuTvDIga85GSFru_QejA.svgz" alt="q_0 q_1 \ge 0" title="q_0 q_1 \ge 0"></span>, and we only have <span class="inline-formula"><img class="img-inline-formula img-formula" width="64" height="15" src="https://math.fontein.de/formulae/lQu6FwZ2i_6iJSlxcVYiLXs9PGBMG2QR1kY_rg.svgz" alt="q_0 q_1 = 0" title="q_0 q_1 = 0"></span> if <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="15" src="https://math.fontein.de/formulae/gP7GbMxNJ5cDWu02PnXKW2XFgXNGbTFB2N0hzg.svgz" alt="q_0 = 0" title="q_0 = 0"></span> or <span class="inline-formula"><img class="img-inline-formula img-formula" width="49" height="12" src="https://math.fontein.de/formulae/adcY0ajGYpIopVUmvdzFS_EG.sDxqJH_XUJIdw.svgz" alt="N = 0" title="N = 0"></span>, we get <span class="inline-formula"><img class="img-inline-formula img-formula" width="77" height="18" src="https://math.fontein.de/formulae/uzRj2zQlt._8vCSBqoi.D1FpBwmeZC.8Z841Uw.svgz" alt="\abs{y_1} > \abs{y_0}" title="\abs{y_1} > \abs{y_0}"></span>.
</p>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/7bOS.gW7YEc_Vl5o5rMonnTQYAeECKSB0p0pwQ.svgz" alt="i \ge 0" title="i \ge 0"></span> resp. <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/Ti11lcyTojLBHDkTVYbO3WV4uEgKYB18h3.rJQ.svgz" alt="i \ge 1" title="i \ge 1"></span>, we proceed by induction. We have <span class="inline-formula"><img class="img-inline-formula img-formula" width="161" height="14" src="https://math.fontein.de/formulae/XYEipjY2jyGXSxqqSV8_qOVDNi6jnUoVBtpU.g.svgz" alt="x_{i+1} = x_{i-1} - q_{i+1} x_i" title="x_{i+1} = x_{i-1} - q_{i+1} x_i"></span>, and <span class="inline-formula"><img class="img-inline-formula img-formula" width="34" height="12" src="https://math.fontein.de/formulae/9R_arkkGHIxOewrTd76DM5bYtzqrdJt.5i.PEQ.svgz" alt="x_{i-1}" title="x_{i-1}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="12" src="https://math.fontein.de/formulae/VZQbcvzzQJvkpFBvkmAxc6N6DT_ZSjLH0wAt8Q.svgz" alt="q_{i+1} x_i" title="q_{i+1} x_i"></span> have different signs; hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="322" height="18" src="https://math.fontein.de/formulae/IlVz4gnF1lj2E_K3c3ZE.W8cujicyZabKgtV.Q.svgz" alt="\abs{x_{i+2}} = \abs{q_i x_{i-1}} + \abs{x_{i-2}} \ge \abs{q_{i+1} x_i} \ge \abs{x_i}" title="\abs{x_{i+2}} = \abs{q_i x_{i-1}} + \abs{x_{i-2}} \ge \abs{q_{i+1} x_i} \ge \abs{x_i}"></span> as <span class="inline-formula"><img class="img-inline-formula img-formula" width="64" height="16" src="https://math.fontein.de/formulae/250kxVkqPkMVn_JUPeQx25JFaN4Y5.gGRq9zHg.svgz" alt="q_{i+1} \neq 0" title="q_{i+1} \neq 0"></span>. Similarly, one gets the result for <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/X.Thp325UI6rFN_8BvGmPz4foMedt_64vdz9tA.svgz" alt="y" title="y"></span>.
</p>
<p>
Note that <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="18" src="https://math.fontein.de/formulae/HA8Y8HCd0zZyoRWDwc3oyjRd38d3wc.KaCuA7w.svgz" alt="\abs{x_{i+2}} = \abs{q_{i+1} x_i}" title="\abs{x_{i+2}} = \abs{q_{i+1} x_i}"></span> if, and only if, <span class="inline-formula"><img class="img-inline-formula img-formula" width="67" height="16" src="https://math.fontein.de/formulae/8vHiv06sHPhfYw3U0OH_7fc2Zo4AJwKs5B8sbA.svgz" alt="x_{i-1} = 0" title="x_{i-1} = 0"></span>; this only happens for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/AP.hyMhQKFwhJ_dXBRqSnJYvMRd9RDeJaL2HKg.svgz" alt="i = 0" title="i = 0"></span>, as for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/i5mcvyDpWMGwXT1XJyBr5nEbjZwc3hX_xbFIfA.svgz" alt="i > 0" title="i > 0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="128" height="18" src="https://math.fontein.de/formulae/kI9M2fWAOeLVn5O7bgjxpuoSYjuqW64wJe6qVw.svgz" alt="\abs{x_{i-1}} \ge \abs{x_0} = 1" title="\abs{x_{i-1}} \ge \abs{x_0} = 1"></span>.
</p>
</li>
<li>
<p>
If <span class="inline-formula"><img class="img-inline-formula img-formula" width="59" height="12" src="https://math.fontein.de/formulae/h.CKxjptyrZ6OMLWJjWZ4rvXJYRihX.wRmfUxA.svgz" alt="n m > 0" title="n m > 0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="19" src="https://math.fontein.de/formulae/pgwT2UHShwBNTZcZjlguFh2xQPVucFtzbAkYvA.svgz" alt="\frac{a_i}{m} \ge 0" title="\frac{a_i}{m} \ge 0"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="20" src="https://math.fontein.de/formulae/5i4CCeX4sVzBGaszgnl7Cdd5qBCiXqZZzyY2Vg.svgz" alt="(-1)^j x_j \ge 0" title="(-1)^j x_j \ge 0"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="109" height="21" src="https://math.fontein.de/formulae/FMB8bGs8i9V.wWsTOb9Fl.NNv4sQlcU5aMHqcw.svgz" alt="(-1)^j \frac{a_i x_j}{m} \ge 0" title="(-1)^j \frac{a_i x_j}{m} \ge 0"></span>.
</p>
<p>
If <span class="inline-formula"><img class="img-inline-formula img-formula" width="59" height="12" src="https://math.fontein.de/formulae/tizN8p3YwxFwsooJx9Sn7FFODzhRXQwOeCaHfA.svgz" alt="n m < 0" title="n m < 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="16" src="https://math.fontein.de/formulae/TBBErkTPTiTWqlZeE9Ct_HZa2O5A44PsQZmt1A.svgz" alt="x_j \ge 0" title="x_j \ge 0"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="8" height="15" src="https://math.fontein.de/formulae/q4ijdcMcwrer_7oZd9BjA6ImUoXNyAWyR9W9Kg.svgz" alt="j" title="j"></span>. First consider the case that <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span> is odd. Then <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> has the same sign as <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="12" src="https://math.fontein.de/formulae/4C14uleBx_VqHXWqIVR_qTIO.9R4eu0eH.pVvw.svgz" alt="a_{-1} = m" title="a_{-1} = m"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="19" src="https://math.fontein.de/formulae/pgwT2UHShwBNTZcZjlguFh2xQPVucFtzbAkYvA.svgz" alt="\frac{a_i}{m} \ge 0" title="\frac{a_i}{m} \ge 0"></span>. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="109" height="21" src="https://math.fontein.de/formulae/FMB8bGs8i9V.wWsTOb9Fl.NNv4sQlcU5aMHqcw.svgz" alt="(-1)^j \frac{a_i x_j}{m} \ge 0" title="(-1)^j \frac{a_i x_j}{m} \ge 0"></span>. Next, consider the case that <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span> is even. Then <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> has the same sign as <span class="inline-formula"><img class="img-inline-formula img-formula" width="63" height="12" src="https://math.fontein.de/formulae/EWZXEM3WXAbX6G1UoEXeXknuEPOi7CaLmFJhvg.svgz" alt="a_{-2} = n" title="a_{-2} = n"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="19" src="https://math.fontein.de/formulae/_gRGm1AWm9xHXzqbHMRLl0TWcH5cRWeAMloxpg.svgz" alt="\frac{a_i}{m} \le 0" title="\frac{a_i}{m} \le 0"></span>. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="109" height="21" src="https://math.fontein.de/formulae/FMB8bGs8i9V.wWsTOb9Fl.NNv4sQlcU5aMHqcw.svgz" alt="(-1)^j \frac{a_i x_j}{m} \ge 0" title="(-1)^j \frac{a_i x_j}{m} \ge 0"></span>.
</p>
<p>
If <span class="inline-formula"><img class="img-inline-formula img-formula" width="59" height="12" src="https://math.fontein.de/formulae/h.CKxjptyrZ6OMLWJjWZ4rvXJYRihX.wRmfUxA.svgz" alt="n m > 0" title="n m > 0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="19" src="https://math.fontein.de/formulae/dP_vlNYfeNSiHB_fJjlz4RgrLESL_m5WXbt2kg.svgz" alt="\frac{a_i}{n} \ge 0" title="\frac{a_i}{n} \ge 0"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="92" height="20" src="https://math.fontein.de/formulae/YlCf9U.YF4qHJkoY3Z6t5hwEkmMT3Z_1BqsyDA.svgz" alt="(-1)^j y_j \le 0" title="(-1)^j y_j \le 0"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="106" height="21" src="https://math.fontein.de/formulae/0WTjQMC_Ylay1HzILcCVqBOfEjSM4_2L6rnpEA.svgz" alt="(-1)^i \frac{a_i y_j}{n} \ge 0" title="(-1)^i \frac{a_i y_j}{n} \ge 0"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="108" height="16" src="https://math.fontein.de/formulae/YGN42SeEZcqoVoO57jRhKhwMkKdEkpHQ2VBDkA.svgz" alt="i = -1, \dots, N" title="i = -1, \dots, N"></span>.
</p>
<p>
If <span class="inline-formula"><img class="img-inline-formula img-formula" width="59" height="12" src="https://math.fontein.de/formulae/tizN8p3YwxFwsooJx9Sn7FFODzhRXQwOeCaHfA.svgz" alt="n m < 0" title="n m < 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="49" height="16" src="https://math.fontein.de/formulae/zGo1HtVIGpHnY0oc5JIdguMwtLT59tWs4T_f0w.svgz" alt="y_j \ge 0" title="y_j \ge 0"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="8" height="15" src="https://math.fontein.de/formulae/q4ijdcMcwrer_7oZd9BjA6ImUoXNyAWyR9W9Kg.svgz" alt="j" title="j"></span>. First consider the case that <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span> is odd. Then <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> has the same sign as <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="12" src="https://math.fontein.de/formulae/4C14uleBx_VqHXWqIVR_qTIO.9R4eu0eH.pVvw.svgz" alt="a_{-1} = m" title="a_{-1} = m"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="19" src="https://math.fontein.de/formulae/c1cTSKqWf9S7hNMz0Pn9WUNd_lxs0YyXeRy6JA.svgz" alt="\frac{a_i}{n} \le 0" title="\frac{a_i}{n} \le 0"></span>. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="106" height="21" src="https://math.fontein.de/formulae/0WTjQMC_Ylay1HzILcCVqBOfEjSM4_2L6rnpEA.svgz" alt="(-1)^i \frac{a_i y_j}{n} \ge 0" title="(-1)^i \frac{a_i y_j}{n} \ge 0"></span>. Next, consider the case that <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span> is even. Then <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> has the same sign as <span class="inline-formula"><img class="img-inline-formula img-formula" width="63" height="12" src="https://math.fontein.de/formulae/EWZXEM3WXAbX6G1UoEXeXknuEPOi7CaLmFJhvg.svgz" alt="a_{-2} = n" title="a_{-2} = n"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="19" src="https://math.fontein.de/formulae/dP_vlNYfeNSiHB_fJjlz4RgrLESL_m5WXbt2kg.svgz" alt="\frac{a_i}{n} \ge 0" title="\frac{a_i}{n} \ge 0"></span>. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="106" height="21" src="https://math.fontein.de/formulae/0WTjQMC_Ylay1HzILcCVqBOfEjSM4_2L6rnpEA.svgz" alt="(-1)^i \frac{a_i y_j}{n} \ge 0" title="(-1)^i \frac{a_i y_j}{n} \ge 0"></span>.
</p>
</li>
<li>
<p>
We show the claim by induction. For <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="13" src="https://math.fontein.de/formulae/TpV8XX6cWvgLDrfsRgJ2NmMpZN1oHih_X3pYXw.svgz" alt="i = -1" title="i = -1"></span>, we have
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="405" height="42" src="https://math.fontein.de/formulae/IHjcTYZW_XBoOMdsSjpgN0yvCZsfv13S6Z2MRA.svgz" alt="\abs{x_{-1}} = 0 < \frac{\abs{m}}{\abs{n}} = \frac{\abs{m}}{\abs{a_{-2}}} \text{ and } \abs{y_{-1}} = 1 \le 1 = \frac{\abs{n}}{\abs{a_{-2}}}." title="\abs{x_{-1}} = 0 < \frac{\abs{m}}{\abs{n}} = \frac{\abs{m}}{\abs{a_{-2}}} \text{ and } \abs{y_{-1}} = 1 \le 1 = \frac{\abs{n}}{\abs{a_{-2}}}.">
</div>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/7bOS.gW7YEc_Vl5o5rMonnTQYAeECKSB0p0pwQ.svgz" alt="i \ge 0" title="i \ge 0"></span>, we have by the induction hypothesis and by <span class="inline-formula"><img class="img-inline-formula img-formula" width="72" height="14" src="https://math.fontein.de/formulae/9HJyyE8oJKSYOtJG3Q4X7w64vppqH3WhwWrAyA.svgz" alt="a_i < a_{i-2}" title="a_i < a_{i-2}"></span>
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="253" height="72" src="https://math.fontein.de/formulae/j6UHvvjra4wQoVbtPk5HbIIbNtTv_T_WUIOnxg.svgz" alt="\abs{\frac{a_i x_{i-1}}{m}} <{} & \abs{\frac{a_{i-2} x_{i-1}}{m}} \le 1 \\
\text{and} \quad \abs{\frac{a_i y_{i-1}}{m}} <{} & \abs{\frac{a_{i-2} y_{i-1}}{m}} \le 1." title="\abs{\frac{a_i x_{i-1}}{m}} <{} & \abs{\frac{a_{i-2} x_{i-1}}{m}} \le 1 \\
\text{and} \quad \abs{\frac{a_i y_{i-1}}{m}} <{} & \abs{\frac{a_{i-2} y_{i-1}}{m}} \le 1.">
</div>
<p>
Now <span class="inline-formula"><img class="img-inline-formula img-formula" width="140" height="21" src="https://math.fontein.de/formulae/U188eLE31PrVoUtlZbpqC3TGUD58pcF5Ah.KOA.svgz" alt="(-1)^{i+1} \frac{a_i x_{i-1}}{m} \ge 0" title="(-1)^{i+1} \frac{a_i x_{i-1}}{m} \ge 0"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="20" src="https://math.fontein.de/formulae/u7I7Jiz_nRE1MWHm8w_DkeU6yP1MVhw.u.j_ig.svgz" alt="\frac{a_i x_{i-1}}{m}" title="\frac{a_i x_{i-1}}{m}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="19" src="https://math.fontein.de/formulae/xifp1LwmIpBl9CSj8oSNM9TgUTncfheTHB3tfQ.svgz" alt="(-1)^{i+1}" title="(-1)^{i+1}"></span> have the same sign. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="140" height="21" src="https://math.fontein.de/formulae/GzV6t8QF6rOUKpucmTPSboPTOIwGe.kItrLUNg.svgz" alt="(-1)^{i+1} \frac{a_i x_{i-1}}{m} \le 1" title="(-1)^{i+1} \frac{a_i x_{i-1}}{m} \le 1"></span>, we get
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="338" height="33" src="https://math.fontein.de/formulae/J1t4HnwIjakp4zhBhxfNAF9jUfOfZf3QhmAaTw.svgz" alt="\abs{\frac{a_i x_{i-1}}{m} + (-1)^i} = \abs{\frac{a_i x_{i-1}}{m} - (-1)^{i+1}} \le 1." title="\abs{\frac{a_i x_{i-1}}{m} + (-1)^i} = \abs{\frac{a_i x_{i-1}}{m} - (-1)^{i+1}} \le 1.">
</div>
<p>
Using <span class="inline-formula"><img class="img-inline-formula img-formula" width="202" height="19" src="https://math.fontein.de/formulae/VIt3EOU0SsOmAWFzBBvGA8adeZY922Ds6zoXTg.svgz" alt="a_i x_{i-1} + (-1)^i m = a_{i-1} x_i" title="a_i x_{i-1} + (-1)^i m = a_{i-1} x_i"></span>, we obtain <span class="inline-formula"><img class="img-inline-formula img-formula" width="108" height="18" src="https://math.fontein.de/formulae/McNIEqbRVb3MyP1iqtFjLWebBF932N63ywVofw.svgz" alt="\abs{a_{i-1} x_i} \le \abs{m}" title="\abs{a_{i-1} x_i} \le \abs{m}"></span>, which gives <span class="inline-formula"><img class="img-inline-formula img-formula" width="91" height="27" src="https://math.fontein.de/formulae/K2Hxa3qB3Nu6qZDV.uqDuSgETWnBoWaJKDf2Iw.svgz" alt="\abs{x_i} \le \frac{\abs{m}}{\abs{a_{i-1}}}" title="\abs{x_i} \le \frac{\abs{m}}{\abs{a_{i-1}}}"></span>.
</p>
<p>
Next, <span class="inline-formula"><img class="img-inline-formula img-formula" width="121" height="21" src="https://math.fontein.de/formulae/OVrtC6IUCWSUkxqsmRreqK2nzPmj2zYOo1GF_w.svgz" alt="(-1)^i \frac{a_i y_{i-1}}{n} \ge 0" title="(-1)^i \frac{a_i y_{i-1}}{n} \ge 0"></span>. Hence, <span class="inline-formula"><img class="img-inline-formula img-formula" width="42" height="19" src="https://math.fontein.de/formulae/CizeV4WjGyEtj0FjlrEdi9PATe8FdS_BG5k8AQ.svgz" alt="(-1)^i" title="(-1)^i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="20" src="https://math.fontein.de/formulae/H7etPRwB5Q8dkTaW61MKSzC6hR7OMwzAaSL8ag.svgz" alt="\frac{a_i y_{i-1}}{n}" title="\frac{a_i y_{i-1}}{n}"></span> have the same sign. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="121" height="21" src="https://math.fontein.de/formulae/JH8PD9MMqnhnaR5xn1U.nBI_TrZ_XvBwIV.qGg.svgz" alt="(-1)^i \frac{a_i y_{i-1}}{n} \le 1" title="(-1)^i \frac{a_i y_{i-1}}{n} \le 1"></span>, we get
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="335" height="33" src="https://math.fontein.de/formulae/qAuBKLi419UKfmsjkz6LGJrdpVDGpzSYVrzyZg.svgz" alt="\abs{\frac{a_i y_{i-1}}{n} + (-1)^{i-1}} = \abs{\frac{a_i y_{i-1}}{n} - (-1)^i} \le 1." title="\abs{\frac{a_i y_{i-1}}{n} + (-1)^{i-1}} = \abs{\frac{a_i y_{i-1}}{n} - (-1)^i} \le 1.">
</div>
<p>
Using <span class="inline-formula"><img class="img-inline-formula img-formula" width="212" height="19" src="https://math.fontein.de/formulae/RpTVvwiVhWSQbjuVNQFOW5.jgwN63m9zZyYp3w.svgz" alt="a_i y_{i-1} + (-1)^{i-1} n = a_{i-1} y_i" title="a_i y_{i-1} + (-1)^{i-1} n = a_{i-1} y_i"></span>, we obtain <span class="inline-formula"><img class="img-inline-formula img-formula" width="98" height="18" src="https://math.fontein.de/formulae/c4jjNIp8I19futBUpeuIBIDNF1QQaUcdH2mkaA.svgz" alt="\abs{a_{i01} y_i} \le \abs{n}" title="\abs{a_{i01} y_i} \le \abs{n}"></span>, which gives the claim.
</p>
</li>
<li>
<p>
Note that for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/Ti11lcyTojLBHDkTVYbO3WV4uEgKYB18h3.rJQ.svgz" alt="i \ge 1" title="i \ge 1"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="92" height="18" src="https://math.fontein.de/formulae/keOvuORlv0syiONjeoHtbaB6PKqXngDF9bp.kA.svgz" alt="\abs{a_{i-1}} > \abs{a_i}" title="\abs{a_{i-1}} > \abs{a_i}"></span>. Hence, in case <span class="inline-formula"><img class="img-inline-formula img-formula" width="121" height="21" src="https://math.fontein.de/formulae/jca.tT3RPKqCn24EE08GCVFwLXPdnj4mrsw_3A.svgz" alt="\abs{a_{i-1}} \le \frac{1}{2} \abs{a_{i-2}}" title="\abs{a_{i-1}} \le \frac{1}{2} \abs{a_{i-2}}"></span>, we are done. Therefore, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="121" height="21" src="https://math.fontein.de/formulae/eDchdx_UNSmKad9r.IzO14u2cya1gO_m3F0tRA.svgz" alt="\abs{a_{i-1}} > \frac{1}{2} \abs{a_{i-2}}" title="\abs{a_{i-1}} > \frac{1}{2} \abs{a_{i-2}}"></span>. Now we required <span class="inline-formula"><img class="img-inline-formula img-formula" width="124" height="18" src="https://math.fontein.de/formulae/QRxF672wnRcnYRVZDVKaEnnqGb0z.Nhz3aSFMg.svgz" alt="\abs{q_i a_{i-1}} \le \abs{a_{i-2}}" title="\abs{q_i a_{i-1}} \le \abs{a_{i-2}}"></span>, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="135" height="21" src="https://math.fontein.de/formulae/ybUMYc9yLVdlm635VtRjEaR_YXDIdw78IjhqlQ.svgz" alt="\frac{1}{2} \abs{q_i a_{i-2}} < \abs{a_{i-2}}" title="\frac{1}{2} \abs{q_i a_{i-2}} < \abs{a_{i-2}}"></span>; but this implies <span class="inline-formula"><img class="img-inline-formula img-formula" width="56" height="18" src="https://math.fontein.de/formulae/CrRBw4uiYjNfH6ywHHtuc.acGBPm.QWGQffSkQ.svgz" alt="\abs{q_i} < 2" title="\abs{q_i} < 2"></span>, i.e. <span class="inline-formula"><img class="img-inline-formula img-formula" width="56" height="18" src="https://math.fontein.de/formulae/vnzbVNQVo2iM6yzvaEde5aTim3gur3WYostzMQ.svgz" alt="\abs{q_i} \le 1" title="\abs{q_i} \le 1"></span>. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="16" src="https://math.fontein.de/formulae/3hZzYqBaVWL4LTbyY1OvdqMOo4ZIffRkGmAe_w.svgz" alt="q_i \neq 0" title="q_i \neq 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="60" height="15" src="https://math.fontein.de/formulae/sxwI6euI9pedQiiIdcprXxIj127RkBJ_LDs0eg.svgz" alt="q_i = \pm 1" title="q_i = \pm 1"></span>.
</p>
<p>
Now <span class="inline-formula"><img class="img-inline-formula img-formula" width="141" height="14" src="https://math.fontein.de/formulae/b9R31mZw9L.hqhVkUoM6j0647i89sGxuy_mdVg.svgz" alt="a_i = a_{i-2} - q_i a_{i-1}" title="a_i = a_{i-2} - q_i a_{i-1}"></span> and both <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="33" height="12" src="https://math.fontein.de/formulae/Svk6ktiqLfKfRt.XxNK0yH7n5zGcMBDBhZPmjQ.svgz" alt="a_{i-2}" title="a_{i-2}"></span> have the same sign, whence <span class="inline-formula"><img class="img-inline-formula img-formula" width="235" height="21" src="https://math.fontein.de/formulae/1kOpVwNSrcoqVRzOX_GJgPnKuCoiB_qeIkJldA.svgz" alt="\abs{a_i} \le \abs{a_{i-2}} - \abs{a_{i-1}} < \frac{1}{2} \abs{a_{i-2}}" title="\abs{a_i} \le \abs{a_{i-2}} - \abs{a_{i-1}} < \frac{1}{2} \abs{a_{i-2}}"></span>.
</p>
</li>
</ol>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
<div class="theorem-environment theorem-proposition-environment">
<div class="theorem-header theorem-proposition-header">
Proposition.
</div>
<div class="theorem-content theorem-proposition-content">
<p>
Assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="67" height="16" src="https://math.fontein.de/formulae/a0xq8Dv9Q3Rk3Gfp.9ZqJ27kXtS6iuyzkn9jdQ.svgz" alt="n, m \neq 0" title="n, m \neq 0"></span>, that <span class="inline-formula"><img class="img-inline-formula img-formula" width="73" height="18" src="https://math.fontein.de/formulae/r66UyyBdKal98xBTZx1VaKQbur9I06wby6eQ7g.svgz" alt="R = K[x]" title="R = K[x]"></span> and that <span class="inline-formula"><img class="img-inline-formula img-formula" width="99" height="19" src="https://math.fontein.de/formulae/F5I1f4OWEum6QQxKt5XolR84B4oVZHkKNAnuVw.svgz" alt="d(f) = q^{\deg f}" title="d(f) = q^{\deg f}"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="16" src="https://math.fontein.de/formulae/zCSih7Xn1ndWUDOhptlOmap7bDld06UaU24wXQ.svgz" alt="f \in R" title="f \in R"></span>. Then:
</p>
<ol class="enum-level-1">
<li>we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="215" height="16" src="https://math.fontein.de/formulae/3K.Gj1d8SCcFyOOeJCJg_CQft.2IGUEuosjj.w.svgz" alt="\deg a_{i-2} = \deg q_i + \deg a_{i-1}" title="\deg a_{i-2} = \deg q_i + \deg a_{i-1}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="16" src="https://math.fontein.de/formulae/akoGZNaPO1zM9aaKuXf2gCydk1epdYbFwpHdvQ.svgz" alt="\deg q_i > 0" title="\deg q_i > 0"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/i5mcvyDpWMGwXT1XJyBr5nEbjZwc3hX_xbFIfA.svgz" alt="i > 0" title="i > 0"></span>;</li>
<li>
<p>
we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="280" height="16" src="https://math.fontein.de/formulae/qcdczAlArXK2L7Nh2g8XfpYAy3fhob0k07dbAQ.svgz" alt="\deg x_0 > \deg q_0 + \deg x_{-1} \ge \deg x_{-1}" title="\deg x_0 > \deg q_0 + \deg x_{-1} \ge \deg x_{-1}"></span>, and
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="336" height="43" src="https://math.fontein.de/formulae/3uGSumiZ5QGUukumHQIr.qBziJneeSXeZg0hlg.svgz" alt="\deg x_i ={} & \deg q_i + \deg x_{i-1} > \deg x_{i-1} \\
\text{and} \quad \deg y_i ={} & \deg q_i + \deg y_{i-1} \ge \deg y_{i-1}" title="\deg x_i ={} & \deg q_i + \deg x_{i-1} > \deg x_{i-1} \\
\text{and} \quad \deg y_i ={} & \deg q_i + \deg y_{i-1} \ge \deg y_{i-1}">
</div>
<p>
for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/qc5XIH5o7W2booQ84E6XQLoB0b2m1BYpkO3g7A.svgz" alt="i = 1, \dots, N" title="i = 1, \dots, N"></span>; hence, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="133" height="16" src="https://math.fontein.de/formulae/Sm5.emrT_DOY7FM.h8O8zi.yd4b4FhUhvCVf9A.svgz" alt="\deg x_i > \deg x_{i-1}" title="\deg x_i > \deg x_{i-1}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/7bOS.gW7YEc_Vl5o5rMonnTQYAeECKSB0p0pwQ.svgz" alt="i \ge 0" title="i \ge 0"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="130" height="16" src="https://math.fontein.de/formulae/A.d2e1KJBtA0Ux_bOxfDyfvOk4_DD52YDBDxMQ.svgz" alt="\deg y_i > \deg y_{i-1}" title="\deg y_i > \deg y_{i-1}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/Ti11lcyTojLBHDkTVYbO3WV4uEgKYB18h3.rJQ.svgz" alt="i \ge 1" title="i \ge 1"></span>;
</p>
</li>
<li>we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="200" height="16" src="https://math.fontein.de/formulae/v8o9IJGuTwDQAyZqFhjCPljCjWsj.RWob5a8qg.svgz" alt="\deg x_i \le \deg m - \deg a_{i-1}" title="\deg x_i \le \deg m - \deg a_{i-1}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="193" height="16" src="https://math.fontein.de/formulae/avwXH.mhO7CW32JZeORpkWbOsQkYkaQW9MIaNQ.svgz" alt="\deg y_i \le \deg n - \deg a_{i-1}" title="\deg y_i \le \deg n - \deg a_{i-1}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="16" src="https://math.fontein.de/formulae/_DQMbAZ3dEtZ9PnpvBNT4KG0SnQg4YQGXa2Hsw.svgz" alt="i = -1, 0, \dots, N" title="i = -1, 0, \dots, N"></span>.</li>
</ol>
</div>
</div>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof.
</div>
<div class="theorem-content theorem-proof-content">
<ol class="enum-level-1">
<li>For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/i5mcvyDpWMGwXT1XJyBr5nEbjZwc3hX_xbFIfA.svgz" alt="i > 0" title="i > 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="219" height="16" src="https://math.fontein.de/formulae/rKv5c9C1uXKalKZC8XcwIi3W7OAh8fxiRIlQvg.svgz" alt="\deg a_i < \deg a_{i-1} < \deg a_{i-2}" title="\deg a_i < \deg a_{i-1} < \deg a_{i-2}"></span>; as <span class="inline-formula"><img class="img-inline-formula img-formula" width="141" height="14" src="https://math.fontein.de/formulae/b9R31mZw9L.hqhVkUoM6j0647i89sGxuy_mdVg.svgz" alt="a_i = a_{i-2} - q_i a_{i-1}" title="a_i = a_{i-2} - q_i a_{i-1}"></span>, we must have <span class="inline-formula"><img class="img-inline-formula img-formula" width="215" height="16" src="https://math.fontein.de/formulae/3K.Gj1d8SCcFyOOeJCJg_CQft.2IGUEuosjj.w.svgz" alt="\deg a_{i-2} = \deg q_i + \deg a_{i-1}" title="\deg a_{i-2} = \deg q_i + \deg a_{i-1}"></span>; this shows <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="16" src="https://math.fontein.de/formulae/akoGZNaPO1zM9aaKuXf2gCydk1epdYbFwpHdvQ.svgz" alt="\deg q_i > 0" title="\deg q_i > 0"></span>.</li>
<li>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/AP.hyMhQKFwhJ_dXBRqSnJYvMRd9RDeJaL2HKg.svgz" alt="i = 0" title="i = 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="62" height="16" src="https://math.fontein.de/formulae/.1fDgxBWVNn_olWEDLuf1h5jaQkkTMIjLrtMMQ.svgz" alt="x_{-1} = 0" title="x_{-1} = 0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="51" height="14" src="https://math.fontein.de/formulae/MEJm6uvT5cjZ0tq0rdtdUrEQFuP_I9sI_gH6dg.svgz" alt="x_0 = 1" title="x_0 = 1"></span>, whence
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="288" height="16" src="https://math.fontein.de/formulae/1WjtuQOsH54LvSOmhLrpPJKqEsvMS5e5.87wxg.svgz" alt="\deg x_0 > \deg q_0 + \deg x_{-1} \ge \deg x_{-1}." title="\deg x_0 > \deg q_0 + \deg x_{-1} \ge \deg x_{-1}.">
</div>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/_Z0Zet3FGKXwxkUDNgJLTR8s1GiVWihuREJy0w.svgz" alt="i = 1" title="i = 1"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="70" height="14" src="https://math.fontein.de/formulae/RrpqeHOyTMDIBDyzQ0oCo6yZ8PBYYTXatstKQA.svgz" alt="y_0 = -q_0" title="y_0 = -q_0"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="102" height="15" src="https://math.fontein.de/formulae/lUr6.dxMhGhaS4354d0ECWeNqq1lCs1GF9h1Rw.svgz" alt="y_1 = 1 + q_0 q_1" title="y_1 = 1 + q_0 q_1"></span>; if <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="15" src="https://math.fontein.de/formulae/gP7GbMxNJ5cDWu02PnXKW2XFgXNGbTFB2N0hzg.svgz" alt="q_0 = 0" title="q_0 = 0"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="254" height="16" src="https://math.fontein.de/formulae/nn5pIp14KiYJCOiR8YTLl_p1obuEU6KOEKvPLQ.svgz" alt="\deg y_1 > \deg q_1 + \deg y_0 \ge \deg y_0" title="\deg y_1 > \deg q_1 + \deg y_0 \ge \deg y_0"></span>. Now assume <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="16" src="https://math.fontein.de/formulae/QOMuL_V_Uf0gc8aD5d5OutFWzzBgHmTjqof.TA.svgz" alt="q_0 \neq 0" title="q_0 \neq 0"></span>; as <span class="inline-formula"><img class="img-inline-formula img-formula" width="78" height="16" src="https://math.fontein.de/formulae/Jow8CN1jsEN5RA9MYrprGal8W94uetLhqGzWVQ.svgz" alt="\deg q_1 > 0" title="\deg q_1 > 0"></span>, we see that
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="398" height="16" src="https://math.fontein.de/formulae/.yjrEykYOmbleONiHM3Tsch8TG9OX3yf5.Pimw.svgz" alt="\deg y_1 = \deg q_0 + \deg q_1 = \deg y_0 + \deg q_1 > \deg y_0." title="\deg y_1 = \deg q_0 + \deg q_1 = \deg y_0 + \deg q_1 > \deg y_0.">
</div>
<p>
Now assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/i5mcvyDpWMGwXT1XJyBr5nEbjZwc3hX_xbFIfA.svgz" alt="i > 0" title="i > 0"></span>. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="143" height="14" src="https://math.fontein.de/formulae/nOjSP4cihuTbR067a3r8bm9lVMOBErh2SjCkWg.svgz" alt="x_i = x_{i-2} - q_i x_{i-1}" title="x_i = x_{i-2} - q_i x_{i-1}"></span>, and we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="151" height="16" src="https://math.fontein.de/formulae/gAehp1NKhzYtUDBkUr9R_.oUI9LLg5DOFVEdkw.svgz" alt="\deg x_{i-1} > \deg x_{i-2}" title="\deg x_{i-1} > \deg x_{i-2}"></span> by induction, we get <span class="inline-formula"><img class="img-inline-formula img-formula" width="176" height="18" src="https://math.fontein.de/formulae/fsWTl8sbmcjRCyEDGEYDWu9.pihktjPMPdVmJQ.svgz" alt="\deg (q_i x_{i-1}) > \deg x_{i-2}" title="\deg (q_i x_{i-1}) > \deg x_{i-2}"></span> and, therefore, <span class="inline-formula"><img class="img-inline-formula img-formula" width="199" height="16" src="https://math.fontein.de/formulae/nWJzQLdajDk3TjtzWQ5XYVsjrWpU6UNbXU6ykw.svgz" alt="\deg x_i = \deg q_i + \deg x_{i-1}" title="\deg x_i = \deg q_i + \deg x_{i-1}"></span>. As <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="16" src="https://math.fontein.de/formulae/akoGZNaPO1zM9aaKuXf2gCydk1epdYbFwpHdvQ.svgz" alt="\deg q_i > 0" title="\deg q_i > 0"></span>, the claim follows. If <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/DfP4so6H6d3XPB13upRbHRBBNQLi.h4E665IYA.svgz" alt="i > 1" title="i > 1"></span>, one obtains the same result for <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/X.Thp325UI6rFN_8BvGmPz4foMedt_64vdz9tA.svgz" alt="y" title="y"></span>.
</p>
</li>
<li>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="13" src="https://math.fontein.de/formulae/TpV8XX6cWvgLDrfsRgJ2NmMpZN1oHih_X3pYXw.svgz" alt="i = -1" title="i = -1"></span>, we have
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="448" height="43" src="https://math.fontein.de/formulae/El2YW0yYpKN1Cnn3NFCQWemKZDRyH8i8uFUu5w.svgz" alt="\deg x_{i-1} ={} & -\infty < \deg m - \deg n = \deg m - \deg a_{-2} \\
\text{and} \quad \deg y_{-1} ={} & 0 \le 0 = \deg n - \deg a_{-2}." title="\deg x_{i-1} ={} & -\infty < \deg m - \deg n = \deg m - \deg a_{-2} \\
\text{and} \quad \deg y_{-1} ={} & 0 \le 0 = \deg n - \deg a_{-2}.">
</div>
<p>
For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="12" src="https://math.fontein.de/formulae/AP.hyMhQKFwhJ_dXBRqSnJYvMRd9RDeJaL2HKg.svgz" alt="i = 0" title="i = 0"></span>, we have
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="366" height="16" src="https://math.fontein.de/formulae/ZO.PH8ijLJxIlJcmravq9Qlt01lXTf1L4sOJ5Q.svgz" alt="\deg x_i = 0 \le \deg m - \deg m = \deg m - \deg a_{-1}" title="\deg x_i = 0 \le \deg m - \deg m = \deg m - \deg a_{-1}">
</div>
<p>
and
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="327" height="70" src="https://math.fontein.de/formulae/zdzVKjPEdmZwqfvbuBqjHKlK4Cg8j5EjpT9QPw.svgz" alt="\deg y_i ={} & \deg q_0 = \deg(q_0 m) - \deg m \\
{}={} & \deg(n - a_0) - \deg m \\
{}\le{} & \deg n - \deg m = \deg n - \deg a_{-1}." title="\deg y_i ={} & \deg q_0 = \deg(q_0 m) - \deg m \\
{}={} & \deg(n - a_0) - \deg m \\
{}\le{} & \deg n - \deg m = \deg n - \deg a_{-1}.">
</div>
<p>
We now continue by induction on <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>. For <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/Ti11lcyTojLBHDkTVYbO3WV4uEgKYB18h3.rJQ.svgz" alt="i \ge 1" title="i \ge 1"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="199" height="16" src="https://math.fontein.de/formulae/nWJzQLdajDk3TjtzWQ5XYVsjrWpU6UNbXU6ykw.svgz" alt="\deg x_i = \deg q_i + \deg x_{i-1}" title="\deg x_i = \deg q_i + \deg x_{i-1}"></span>; as
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="437" height="18" src="https://math.fontein.de/formulae/VGJDnAqGYoINnSRhvK2mvjKOErV.Bn0JMXC3wA.svgz" alt="\deg q_i = \deg (a_{i-2} - a_i) - \deg a_{i-1} \le \deg a_{i-2} - \deg a_{i-1}" title="\deg q_i = \deg (a_{i-2} - a_i) - \deg a_{i-1} \le \deg a_{i-2} - \deg a_{i-1}">
</div>
<p>
and – by induction – <span class="inline-formula"><img class="img-inline-formula img-formula" width="218" height="16" src="https://math.fontein.de/formulae/arO30ms3NMTe3OT.N6kaTefFJprSF1Ha.u3VGw.svgz" alt="\deg x_{i-1} \le \deg m - \deg a_{i-2}" title="\deg x_{i-1} \le \deg m - \deg a_{i-2}"></span> we obtain
</p>
<div class="align-formula">
<img class="img-align-formula img-formula" width="396" height="44" src="https://math.fontein.de/formulae/YfJMSF5qzp1evOtpoLEIwyiOw6c4gPxQYsKwXw.svgz" alt="\deg x_i \le{} & (\deg a_{i-2} - \deg a_{i-1}) + (\deg m - \deg a_{i-2}) \\
{}={} & \deg m - \deg a_{i-1}." title="\deg x_i \le{} & (\deg a_{i-2} - \deg a_{i-1}) + (\deg m - \deg a_{i-2}) \\
{}={} & \deg m - \deg a_{i-1}.">
</div>
<p>
Similarly, we obtain <span class="inline-formula"><img class="img-inline-formula img-formula" width="193" height="16" src="https://math.fontein.de/formulae/avwXH.mhO7CW32JZeORpkWbOsQkYkaQW9MIaNQ.svgz" alt="\deg y_i \le \deg n - \deg a_{i-1}" title="\deg y_i \le \deg n - \deg a_{i-1}"></span>.
</p>
</li>
</ol>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
<p>
Hence, we obtain:
</p>
<div class="theorem-environment theorem-corollary-environment">
<div class="theorem-header theorem-corollary-header">
Corollary.
</div>
<div class="theorem-content theorem-corollary-content">
<p>
If <span class="inline-formula"><img class="img-inline-formula img-formula" width="49" height="12" src="https://math.fontein.de/formulae/gPtnrnCRKvU6tn.YsAQGByPRdRPTop12CSmtnA.svgz" alt="R = \Z" title="R = \Z"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="74" height="18" src="https://math.fontein.de/formulae/JyWTOzqZOxYOQtpoUG0aaYdScFa.LzN8FUE98w.svgz" alt="d(z) = \abs{z}" title="d(z) = \abs{z}"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="42" height="13" src="https://math.fontein.de/formulae/XtGZOZkBTPhMI_D4hlZYkj88d2DK4hHcnUBKpQ.svgz" alt="z \in \Z" title="z \in \Z"></span>, or <span class="inline-formula"><img class="img-inline-formula img-formula" width="73" height="18" src="https://math.fontein.de/formulae/r66UyyBdKal98xBTZx1VaKQbur9I06wby6eQ7g.svgz" alt="R = K[x]" title="R = K[x]"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="99" height="19" src="https://math.fontein.de/formulae/F5I1f4OWEum6QQxKt5XolR84B4oVZHkKNAnuVw.svgz" alt="d(f) = q^{\deg f}" title="d(f) = q^{\deg f}"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="16" src="https://math.fontein.de/formulae/zCSih7Xn1ndWUDOhptlOmap7bDld06UaU24wXQ.svgz" alt="f \in R" title="f \in R"></span>, and if the <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="11" src="https://math.fontein.de/formulae/9Zv2E.GBERyjqgYtQWmv6ZHV8XYFW13z69al9Q.svgz" alt="q_i" title="q_i"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="15" height="10" src="https://math.fontein.de/formulae/gaaA6xMXGApRM7gbUzpx9BMSmBeM_JT.oIbP7Q.svgz" alt="a_i" title="a_i"></span> are chosen such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="147" height="18" src="https://math.fontein.de/formulae/S2wcGTeyBKL9nWyJvzpE8RGEK_1Sp3Yd4HByqA.svgz" alt="\abs{a_i - a_{i-2}} \le \abs{a_{i-2}}" title="\abs{a_i - a_{i-2}} \le \abs{a_{i-2}}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="39" height="14" src="https://math.fontein.de/formulae/7bOS.gW7YEc_Vl5o5rMonnTQYAeECKSB0p0pwQ.svgz" alt="i \ge 0" title="i \ge 0"></span>, we have the following:
</p>
<ol class="enum-level-1">
<li>for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/v7audDREWLvwbLnxGi1y1g0YI9wPKye.BRA68Q.svgz" alt="i = 0, \dots, N" title="i = 0, \dots, N"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="120" height="18" src="https://math.fontein.de/formulae/TxBmuK1VaFLBcl5LpYRC8GA99bYtSUJyUqycPQ.svgz" alt="d(x_i) > d(x_{i-1})" title="d(x_i) > d(x_{i-1})"></span>; for <span class="inline-formula"><img class="img-inline-formula img-formula" width="94" height="16" src="https://math.fontein.de/formulae/qc5XIH5o7W2booQ84E6XQLoB0b2m1BYpkO3g7A.svgz" alt="i = 1, \dots, N" title="i = 1, \dots, N"></span>, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="112" height="18" src="https://math.fontein.de/formulae/rzCAKIHSrMIw5_Rm4T3Zqe_m4L637Z7Qjb_FYA.svgz" alt="d(y_i) > d(y_{-1})" title="d(y_i) > d(y_{-1})"></span>;</li>
<li>we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="114" height="27" src="https://math.fontein.de/formulae/F444_m14jCORQHSZP1Bc22L6lxrhLuvznADwkA.svgz" alt="d(x_i) \le \frac{d(m)}{d(a_{i-1})}" title="d(x_i) \le \frac{d(m)}{d(a_{i-1})}"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="113" height="27" src="https://math.fontein.de/formulae/9htlY7bmWq5op_ghFwidMMq8PTXo7W1cdQ5BXg.svgz" alt="d(y_i) \le \frac{d(n)}{d(a_{i-1})}" title="d(y_i) \le \frac{d(n)}{d(a_{i-1})}"></span> for <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="16" src="https://math.fontein.de/formulae/_DQMbAZ3dEtZ9PnpvBNT4KG0SnQg4YQGXa2Hsw.svgz" alt="i = -1, 0, \dots, N" title="i = -1, 0, \dots, N"></span>; in particular, we have <span class="inline-formula"><img class="img-inline-formula img-formula" width="208" height="27" src="https://math.fontein.de/formulae/vwlr6yEGhykE40Dli19TMr0izUDByo2NpUdqJA.svgz" alt="d(x_{N-1}) < \frac{d(m)}{d(a_{N-1})} \le d(m)" title="d(x_{N-1}) < \frac{d(m)}{d(a_{N-1})} \le d(m)"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="201" height="27" src="https://math.fontein.de/formulae/nL0sBRRIODFEk24oy9lDD_gAN8D4jPhgMOJ0uA.svgz" alt="d(y_{N-1}) < \frac{d(n)}{d(a_{N-1})} \le d(n)" title="d(y_{N-1}) < \frac{d(n)}{d(a_{N-1})} \le d(n)"></span>.</li>
</ol>
</div>
</div>
<div class="theorem-environment theorem-proof-environment qed">
<div class="theorem-header theorem-proof-header">
Proof.
</div>
<div class="theorem-content theorem-proof-content">
<p>
We are left to show the last statement of 2. For that, note that <span class="inline-formula"><img class="img-inline-formula img-formula" width="289" height="27" src="https://math.fontein.de/formulae/SLZBcvdpznfGNH8yRTNTw0yxwHiD1VHPqYLiww.svgz" alt="d(x_{N-1}) \le \frac{d(m)}{d(a_{N-2})} < \frac{d(m)}{d(a_{N-1})} \le d(m)" title="d(x_{N-1}) \le \frac{d(m)}{d(a_{N-2})} < \frac{d(m)}{d(a_{N-1})} \le d(m)"></span> and, analogously, <span class="inline-formula"><img class="img-inline-formula img-formula" width="201" height="27" src="https://math.fontein.de/formulae/nL0sBRRIODFEk24oy9lDD_gAN8D4jPhgMOJ0uA.svgz" alt="d(y_{N-1}) < \frac{d(n)}{d(a_{N-1})} \le d(n)" title="d(y_{N-1}) < \frac{d(n)}{d(a_{N-1})} \le d(n)"></span>.
</p>
</div>
<div class="qed-block"><span class="qed-sign"></span></div>
</div>
</div>