Arithmetic of Gaussian integers

Štefan Porubský

Institute of Computer Science of the Academy of Sciences of the Czech Republic
Prague

Abstract

A Gaussian integer is an expression of the form x+yi, where x and y are (rational) integers, and i is defined by (i^2)=-1. The Gaussian integers form the ring ℤ[i]={x+yi:x,y ∈ℤ}=ℤ+iℤ, with ordinary addition and multiplication of complex numbers.  ℤ[i] is a Euclidean domain with respect to the absolute value |·|, where the Euclidean steps can be computed as least remainder divisions. This is probably base for some MATHEMATICA commands as PrimeQ, FactorInteger, Divisors, and GCD which work when GaussianIntegers options is turned on. In the talk we shall implement algorithms for Gaussian integers for less common complete residue systems, division algorithms, Gaussian numeration systems, or for doing arithmetic without separation into real and imaginary part, and several forms of the GCD