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
The interesting thing about Gaussian Integers is that they are similar to integers in the way that all 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 .

---

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.