Most, if not all reading should be acquainted with the set of complex numbers
, usually this comes from dealing with special polynomials, such as those of the form
. We introduce the
Gaussian Integers, brought forth by Gauss in 1832. As one can guess, these integers comprise the set
![$$\mathbb{Z}[i] = \{a+bi \mid a,b \in \mathbb{Z} \}$$](//latex.artofproblemsolving.com/e/2/3/e234c54f7c35ad18507e354b7fd7a71b796b903a.png)
The interesting thing about Gaussian Integers is that they are similar to integers in the way that all
![$x \in \mathbb{Z}[i]$](//latex.artofproblemsolving.com/6/6/f/66f7af55ca437c2f1d114531c7f1bcf16939ab51.png)
can be factored into unique primes. As an example, we look at the factorization of
:
Right now you have to take my word for it, but all four of these factors are prime. We see here that there are two possible factorizations, which seems to contradict the uniqueness of a prime factorization. We
know* that the integers form a unique factorization domain, but look at this:
Are these two different factorizations? In essence, no. These factorizations differ by the multiplication of a
unit, in this case elements
in
or
such that there exists another element in that set
such that
, the multiplicative identity.
Looking closely at the prime factorizations, we can't tell for sure right now that
and
are indeed prime.
We can deal with the general case by noting a key fact, if
is not a Gaussian prime, then
for some
. Using this, assume
is a Gaussian prime, with
. Then,
is not a Gaussian prime. Assume
is not prime, that is for some
, 
. Then,
or
(why?). We know that
as
is a Gaussian prime, this means that
or
(why?). Thus,
(why?) contradicting our assumption. Now, let
, we call this the
norm of
. We have just shown that if
is Gaussian prime, then
is prime. We stop here to note the useful fact that the norm is multiplicative, that is:
We would also like to show that if
is prime, then
is a Gaussian prime. To do this we write down the prime factorization:
. The specific prime factorization does not matter. Just note that:
where
is a prime. We then switch to the contrapositive:
If is not a Gaussian prime, then is not prime. By the above, we see this is obviously true.
*If you are familiar with the proof of unique factorization in 
, try inducting on the norm to prove it in ![$\mathbb{Z}[i]$](//latex.artofproblemsolving.com/c/7/9/c79ec4020beb2bd23555dfd7289612faf19d5959.png)
.
We have obviously dealt with showing the numbers we assumed were Gaussian primes before were in fact Gaussian primes(still remember them?), but we left out a case in the first demonstration. We proved that the norm is prime for Gaussian primes with imaginary part not zero, i.e.
. This is obviously untrue for
. So what are the Gaussian primes on the real axis? One might guess all primes are Gaussian primes, but this would be close, but very far from the truth:
This is such because
is real, so might be able to be written as
. In this case we have found the sufficient
. So, if
is a real Gaussian prime, then
. Straight away we can see if
, 
as the RHS is at most
. Suprisingly, for any
, for some
we have
. An elegant proof credited to Dedekind is given below, although a bit out of scope for this post.
Let
be a prime number. By
Euler's Criterion there exists an
such that
. Simplifying, we see this implies
, or that there exists an
such that
is divisible by
. We write this as
. Note that
(why?). Thus
and
contain factors such that when multiplied,
divides their product. Thus, at best,
divides the product of two or more factors, but can't divide just one, and hence is not prime. It follows then that
for some
. This yields
.
We understand fully when a Gaussian integer
is prime, this is when:
The norm 
is prime, and 
.
and 
and is prime.
Now we can have more of a visual understanding of these Gaussian primes, as I have programmed a complex plane viewer, which produced these nice images:
With primes out of the way, we can talk about arithmetic in the Gaussian integers. In the integers, we can use induction to prove that for any integers
, can be written as
, where
. This can be shown to hold in a similar way for Gaussian integers, and the takeaway here is that writing a number in this form shows the least remainder and quotient obtained from a division algorithm. Here is the statement for Gaussian integers:
For any two Gaussian integers
and
, can be written as
, where
. Obviously this isn't satisfactory to simply hear, one must see. Before we visualize, realize that is we are not providing a rigorous proof, we simply mean to show how one can pick a
and thus why
. We start by expanding
. We then look solely at the
term.
where
. Now we can visualize. Remember that
and
may be any integer. We view
and
as
vectors, one rotated 90 degrees from the other(why?).
Now
can be any integer, so we consider all linear combinations of these vectors, that is
and
scale the two, then we add the vectors. All the possible values of
is shown by the intersection points in the image. Note that squares form as they are 90 degrees apart(what else makes them squares?).
We know
can be any point on this grid, so we now know what to do about the bounds on
, seeing
is the distance from the nearest intersection point. We know the minimum that
can be
, and the maximum distance is obtained when
is in the center of a square, when
. This is show in the below image, the middle dot being the place
has to be to maximize
, with the circles represent the area swept out by all points
away from an intersection point.
Finally, we can talk about modular arithmetic. We define modular arithmetic in the same way we do in
, that is
iff
. Many useful things can be done with this modular arithmetic, and it is very close to modular arithmetic in
. Geometrically, we see the number of residues modulo
is the number all the Gaussian integers in or on the sides, not corners, of a square of the many squares formed by considering linear combinations of
and
, as we saw from looking at remainders from division algorithms. Note that in the integers, the number of non-zero residues modulo
is
. Let
represent the amount of residues modulo
. The analog of
Fermat's Little Theorem turns out to be true.
Let
be a Gaussian prime. If
, then
We need a small affirmation, that is the existence of an inverse. We need to prove the there exist an
such that
if and share no factors(why?). To prove this we write it as
. We note there exists
that fulfill this as
Bezout's lemma applies, because it is essentially the division algorithm run in reverse. (what division algorithm? try finding one for Gaussian integers!).
We prove this in the way we normally prove the theorem. Let
be the distinct residues modulo
, and set
. Consider the sequence
.
Assume, for the sake of contradiction, for some
and
, that
. We multiply both sides by
, and we obtain that
. This is absurd, as we have each residue being distinct.
Thus, all residues of the sequence
are distinct, and thus,
. Multiplying both sides by
, which exists since
is a Gaussian prime and hence all non-zero residues are co-prime to
, we arrive at
. Note that the proof of the analog of
Euler's Totient Theorem is exactly this.
We have just one more thing to deal with, what is
? There are a few things that need to be proved, which is left to you to prove.
1.
(think geometrically)
2.
(combinatorics)
3.
(expand and substitute as much as possible)
Using these facts, we have that:
Thus,
. That is quite surprising, and I end this post with the theorem once more, for
co-prime to a Gaussian
, we have that:
Thank you for reading.
This post has been edited 1 time. Last edited by always_correct, Nov 29, 2016, 2:53 AM
by CJB19, May 15, 2025, 4:02 PM 
and 
intersect at the point 
.
?
,
.
are chosen from 0 to 1. What is the probability that their positive difference is more than 
?
?
families, there are 
children respectively. If a random child from any of the families is chosen, what is the probability that the child has 
siblings? Express your answer as a common fraction.
,
people, exactly 
such that 
.
,
lies on diagonal 
such that 
.
.
has 
,
,
.
.
so 
and since 
is just 
therefore 
so 
,
.![$$\mathbb{Z}[i] = \{a+bi \mid a,b \in \mathbb{Z} \}$$](http://latex.artofproblemsolving.com/e/2/3/e234c54f7c35ad18507e354b7fd7a71b796b903a.png)
The interesting thing about Gaussian Integers is that they are similar to integers in the way that all ![$x \in \mathbb{Z}[i]$](http://latex.artofproblemsolving.com/6/6/f/66f7af55ca437c2f1d114531c7f1bcf16939ab51.png)
can be factored into unique primes. As an example, we look at the factorization of 
:
Right now you have to take my word for it, but all four of these factors are prime. We see here that there are two possible factorizations, which seems to contradict the uniqueness of a prime factorization. We know* that the integers form a unique factorization domain, but look at this:
Are these two different factorizations? In essence, no. These factorizations differ by the multiplication of a unit, in this case elements 
in 
or 
such that 
,
and 
are indeed prime.
is not a Gaussian prime, then 
for some 
.
is a Gaussian prime, with 
.
is not a Gaussian prime. Assume 
is not prime, that is for some 
,
.
or 
(why?). We know that 
as 
is a Gaussian prime, this means that 
or 
(why?). Thus, 
(
,
.
is Gaussian prime, then 
is prime. We stop here to note the useful fact that the norm is multiplicative, that is:
We would also like to show that if 
is prime, then 
.
where 
is a prime. We then switch to the contrapositive: If 
,![$\mathbb{Z}[i]$](http://latex.artofproblemsolving.com/c/7/9/c79ec4020beb2bd23555dfd7289612faf19d5959.png)
.
.
.
This is such because 
.
.
is a real Gaussian prime, then 
.
,
as the RHS is at most 
.
,
.
.
,
such that 
is divisible by 
.
(
and 
contain factors such that when multiplied, 
for some 
.
is prime, this is when:
is prime, and 
.
and 
and 
,
,
.
,
,
.
.
term.
where 
.
may be any integer. We view 
as vectors, one rotated 90 degrees from the other(why?).
is shown by the intersection points in the image. Note that squares form as they are 90 degrees apart(what else makes them squares?).
,
is the distance from the nearest intersection point. We know the minimum that 
,
.
iff 
.
,
.
represent the amount of residues modulo 
,
if 
.
be the distinct residues modulo 
.
.
and 
,
.
,
.
.
,
.
?
(think geometrically)
(combinatorics)
(expand and substitute as much as possible)
Thus, 
.
Thank you for reading.
July 2017
December 2016