Editing Euclidean algorithm (section)

=== Gaussian integers ===
[[File:Gaussian primes.svg|thumb|alt="A set of dots lying within a circle. The pattern of dots has fourfold symmetry, i.e., rotations by 90 degrees leave the pattern unchanged. The pattern can also be mirrored about four lines passing through the center of the circle: the vertical and horizontal axes, and the two diagonal lines at ±45 degrees."|Distribution of Gaussian primes {{math|''u'' + ''vi''}} in the complex plane, with norms {{math|''u''<sup>2</sup> + ''v''<sup>2</sup>}} less than 500]]

The [[Gaussian integer]]s are [[complex number]]s of the form {{math|1=''α'' = ''u'' + ''vi''}}, where {{mvar|u}} and {{mvar|v}} are ordinary [[integer]]s<ref group=note>The phrase "ordinary integer" is commonly used for distinguishing usual integers from Gaussian integers, and more generally from [[algebraic integer]]s.</ref> and {{mvar|i}} is the [[imaginary unit|square root of negative one]].<ref name="Stillwell_2003" /> By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument [[#Bézout's identity|above]].<ref name="Gauss_1832">{{cite journal | author-link = Carl Friedrich Gauss|last=Gauss|first=C. F. | year = 1832 | title = Theoria residuorum biquadraticorum | journal = Comm. Soc. Reg. Sci. Gött. Rec. | volume = 4}} Reprinted in {{cite book|first=C. F.|last=Gauss|year=2011|chapter=Theoria residuorum biquadraticorum commentatio prima |title=Werke|volume=2|publisher=Cambridge Univ. Press|pages=65–92|doi=10.1017/CBO9781139058230.004|isbn=9781139058230}} and {{cite book|first=C. F.|last=Gauss|year=2011|chapter=Theoria residuorum biquadraticorum commentatio secunda|title=Werke|volume=2|publisher=Cambridge Univ. Press|pages=93–148|doi=10.1017/CBO9781139058230.005|isbn=9781139058230}}</ref> This unique factorization is helpful in many applications, such as deriving all [[Pythagorean triple]]s or proving [[Fermat's theorem on sums of two squares]].<ref name="Stillwell_2003">{{Harvnb|Stillwell|2003|pp=101–116}}</ref> In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.

The Euclidean algorithm developed for two Gaussian integers {{mvar|α}} and {{mvar|β}} is nearly the same as that for ordinary integers,<ref name="hensley">{{cite book|title=Continued Fractions|first=Doug|last=Hensley|publisher=World Scientific|year=2006|isbn=9789812564771|page=26|url=https://books.google.com/books?id=k3PVXFkweKgC&pg=PA26}}</ref> but differs in two respects. As before, we set {{math|1=''r''<sub>−2</sub> = ''α''}} and {{math|1=''r''<sub>−1</sub> = ''β''}}, and the task at each step {{mvar|k}} is to identify a quotient {{math|''q''<sub>''k''</sub>}} and a remainder {{math|''r''<sub>''k''</sub>}} such that
: <math>r_k = r_{k-2} - q_k r_{k-1},</math>
where every remainder is strictly smaller than its predecessor: {{math|{{mabs|''r''<sub>''k''</sub>}} &lt; {{mabs|''r''<sub>''k''−1</sub>}}}}. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are [[complex number]]s. The quotients {{math|''q''<sub>''k''</sub>}} are generally found by rounding the real and complex parts of the exact ratio (such as the complex number {{math|''α''/''β''}}) to the nearest integers.<ref name="hensley"/> The second difference lies in the necessity of defining how one complex remainder can be "smaller" than another. To do this, a [[norm (mathematics)|norm function]] {{math|1=''f''(''u'' + ''vi'') = ''u''<sup>2</sup> + ''v''<sup>2</sup>}} is defined, which converts every Gaussian integer {{math|''u'' + ''vi''}} into an ordinary integer. After each step {{mvar|k}} of the Euclidean algorithm, the norm of the remainder {{math|''f''(''r''<sub>''k''</sub>)}} is smaller than the norm of the preceding remainder, {{math|''f''(''r''<sub>''k''−1</sub>)}}. Since the norm is a nonnegative integer and decreases with every step, the Euclidean algorithm for Gaussian integers ends in a finite number of steps.<ref>{{cite book|title=Theory of Algebraic Integers|series=Cambridge Mathematical Library|first=Richard|last=Dedekind|author-link=Richard Dedekind|publisher=Cambridge University Press|year=1996|isbn=9780521565189|pages=22–24|url=https://books.google.com/books?id=KZRBabJY4ewC&pg=PA222}}</ref> The final nonzero remainder is {{math|gcd(''α'', ''β'')}}, the Gaussian integer of largest norm that divides both {{mvar|α}} and {{mvar|β}}; it is unique up to multiplication by a unit, {{math|±1}} or {{math|±''i''}}.<ref>{{cite book|title=Numbers and Symmetry: An Introduction to Algebra|first1=Bernard L.|last1=Johnston|first2=Fred|last2=Richman|publisher=CRC Press|year=1997|isbn=9780849303012|page=44|url=https://books.google.com/books?id=koUfrlgsmUcC&pg=PA44}}</ref>

Many of the other applications of the Euclidean algorithm carry over to Gaussian integers. For example, it can be used to solve linear Diophantine equations and Chinese remainder problems for Gaussian integers;<ref>{{cite book|title=Introduction to Number Theory|url=https://archive.org/details/introductiontonu0000adam|url-access=registration|first1=William W.|last1=Adams|first2=Larry Joel|last2=Goldstein|publisher=Prentice-Hall|year=1976|isbn=9780134912820|at=Exercise 24, p.&nbsp;205|quote=State and prove an analogue of the Chinese remainder theorem for the Gaussian integers.}}</ref> continued fractions of Gaussian integers can also be defined.<ref name="hensley"/>