Editing Gaussian integer (section)

=={{Anchor|gcd}}Greatest common divisor==
As for any [[unique factorization domain]], a ''[[greatest common divisor]] (gcd)'' of two Gaussian integers {{math|''a'', ''b''}} is a Gaussian integer {{math|''d''}} that is a common divisor of {{math|''a''}} and {{math|''b''}}, which has all common divisors of {{math|''a''}} and {{math|''b''}} as divisor. That is (where {{math|{{!}}}} denotes the [[divisibility]] relation),

*{{math|''d'' {{!}} ''a''}} and {{math|''d'' {{!}} ''b''}}, and
*{{math|''c'' {{!}} ''a''}} and {{math|''c'' {{!}} ''b''}} implies {{math|''c'' {{!}} ''d''}}.
Thus, ''greatest'' is meant relatively to the divisibility relation, and not for an ordering of the ring (for integers, both meanings of ''greatest'' coincide).

More technically, a greatest common divisor of {{math|''a''}} and {{math|''b''}} is a [[ideal (ring theory)#Ideal generated by a set|generator]] of the [[ideal (ring theory)|ideal]] generated by {{math|''a''}} and {{math|''b''}} (this characterization is valid for [[principal ideal domain]]s, but not, in general, for unique factorization domains).

The greatest common divisor of two Gaussian integers is not unique, but is defined up to the multiplication by a [[unit (ring theory)|unit]]. That is, given a greatest common divisor {{math|''d''}} of {{math|''a''}} and {{math|''b''}}, the greatest common divisors of {{math|''a''}} and {{math|''b''}} are {{math|''d'', −''d'', ''id''}}, and {{math|−''id''}}.

There are several ways for computing a greatest common divisor of two Gaussian integers {{math|''a''}} and {{math|''b''}}. When one knows the prime factorizations of {{math|''a''}} and {{math|''b''}},
:<math>a = i^k\prod_m {p_m}^{\nu_m}, \quad b = i^n\prod_m {p_m}^{\mu_m},</math>
where the primes {{math|''p<sub>m</sub>''}} are pairwise non associated, and the exponents {{math|''μ<sub>m</sub>''}} non-associated, a greatest common divisor is
:<math>\prod_m {p_m}^{\lambda_m},</math>
with
:<math>\lambda_m = \min(\nu_m, \mu_m).</math>

Unfortunately, except in simple cases, the prime factorization is difficult to compute, and [[Euclidean algorithm]] leads to a much easier (and faster) computation. This algorithm consists of replacing of the input {{math|(''a'', ''b'')}} by {{math|(''b'', ''r'')}}, where {{math|''r''}} is the remainder of the Euclidean division of {{math|''a''}} by {{math|''b''}}, and repeating this operation until getting a zero remainder, that is a pair {{math|(''d'', 0)}}. This process terminates, because, at each step, the norm of the second Gaussian integer decreases. The resulting {{math|''d''}} is a greatest common divisor, because (at each step) {{math|''b''}} and {{math|1=''r'' = ''a'' − ''bq''}} have the same divisors as {{math|''a''}} and {{math|''b''}}, and thus the same greatest common divisor.

This method of computation works always, but is not as simple as for integers because Euclidean division is more complicated. Therefore, a third method is often preferred for hand-written computations. It consists in remarking that the norm {{math|''N''(''d'')}} of the greatest common divisor of {{math|''a''}} and {{math|''b''}} is a common divisor of {{math|''N''(''a'')}}, {{math|''N''(''b'')}}, and {{math|''N''(''a'' + ''b'')}}. When the greatest common divisor {{math|''D''}} of these three integers has few factors, then it is easy to test, for common divisor, all Gaussian integers with a norm dividing {{math|''D''}}.

For example, if {{math|1=''a'' = 5 + 3''i''}}, and {{math|1=''b'' = 2 − 8''i''}}, one has {{math|1=''N''(''a'') = 34}}, {{math|1=''N''(''b'') = 68}}, and {{math|1=''N''(''a'' + ''b'') = 74}}. As the greatest common divisor of the three norms is 2, the greatest common divisor of {{math|''a''}} and {{math|''b''}} has 1 or 2 as a norm. As a gaussian integer of norm 2 is necessary associated to {{math|1 + ''i''}}, and as {{math|1 + ''i''}} divides {{math|''a''}} and {{math|''b''}}, then the greatest common divisor is {{math|1 + ''i''}}.

If {{math|''b''}} is replaced by its conjugate {{math|1=''b'' = 2 + 8''i''}}, then the greatest common divisor of the three norms is 34, the norm of {{math|''a''}}, thus one may guess that the greatest common divisor is {{math|''a''}}, that is, that {{math|''a'' {{!}} ''b''}}. In fact, one has {{math|1=2 + 8''i'' = (5 + 3''i'')(1 + ''i'')}}.