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 + vi) = u² + v² 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.

---

---