Gaussian integer
Describing residue classes

Given a modulus z, all elements of a residue class have the same remainder for the Euclidean division by z, provided one uses the division with unique quotient and remainder, which is described above. Thus enumerating the residue classes is equivalent with enumerating the possible remainders. This can be done geometrically in the following way.

In the complex plane, one may consider a square grid, whose squares are delimited by the two lines

with s and t integers (blue lines in the figure). These divide the plane in semi-open squares (where m and n are integers)

The semi-open intervals that occur in the definition of Q have been chosen in order that every complex number belong to exactly one square; that is, the squares Q form a partition of the complex plane. One has

This implies that every Gaussian integer is congruent modulo z to a unique Gaussian integer in Q (the green square in the figure), which its remainder for the division by z. In other words, every residue class contains exactly one element in Q.

The Gaussian integers in Q (or in its boundary) are sometimes called minimal residues because their norm are not greater than the norm of any other Gaussian integer in the same residue class (Gauss called them absolutely smallest residues).

From this one can deduce by geometrical considerations, that the number of residue classes modulo a Gaussian integer z = a + bi equals its norm N (z) = a + b (see below for a proof; similarly, for integers, the number of residue classes modulo n is its absolute value | n |).

The relation Q = (m + in) z + Q means that all Q are obtained from Q by translating it by a Gaussian integer. This implies that all Q have the same area N = N (z), and contain the same number n of Gaussian integers.

Generally, the number of grid points (here the Gaussian integers) in an arbitrary square with the area A is A + Θ (√ A) (see Big theta for the notation). If one considers a big square consisting of k × k squares Q, then it contains k N + O (k √ N) grid points. It follows k n = k N + Θ (k √ N), and thus n = N + Θ (√ N / k), after a division by k. Taking the limit when k tends to the infinity gives n = N = N (z).
detectable_content:number_placeholders[4]