# Gaussian Primes

The Gaussian integers are [complex numbers] of the form $α = u + vi$, where *u* and *v* are ordinary [integers] and *i* is the [square root of negative one]. By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument [above]. This unique factorization is helpful in many applications, such as deriving all [Pythagorean triples] or proving [Fermat’s theorem on sums of two squares]. 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 α and β is nearly the same as that for normal integers, but differs in two respects. As before, the task at each step *k* is to identify a quotient *q*_{k} and a remainder *r*_{k} such that where *r*_{k−2} = α, *r*_{k−1} = β, and every remainder is strictly smaller than its predecessor, |*r*_{k}| < |*r*_{k−1}|. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are [complex numbers]. The quotients *q*_{k} are generally found by rounding the real and complex parts of the exact ratio (such as the complex number α/β) to the nearest integers.[^5] The second difference lies in the necessity of defining how one complex remainder can be “smaller” than another. To do this, a [norm function]
*f*(*u* + *v*i) = *u*^{2} + *v*^{2} is defined, which converts every Gaussian integer *u* + *vi* into a normal integer. After each step *k* of the Euclidean algorithm, the norm of the remainder *f*(*r*_{k}) is smaller than the norm of the preceding remainder, *f*(*r*_{k−1}). 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.