This site is supported by donations to The OEIS Foundation.

# Gaussian integers

(Redirected from Gaussian integer)

A Gaussian integer is a complex number ${\displaystyle a+bi}$ such that the real part is a real integer and the imaginary part is a real integer multiplied by the imaginary unit ${\displaystyle i={\sqrt {-1}}}$. Purely real integers may be considered Gaussian integers having an imaginary part of 0. The usual symbol for the ring of Gaussian integers is ${\displaystyle \mathbb {Z} [i]}$, but ${\displaystyle \mathbb {G} }$ and ${\displaystyle \mathbb {A} (-1)}$[1] have also been used. In set notation, we may readily write ${\displaystyle \mathbb {Z} [i]\subset \mathbb {C} }$, but ${\displaystyle \mathbb {Z} \subset \mathbb {Z} [i]}$ is not a completely straightforward proposition, as well shall see later on.

The complex units 1, ${\displaystyle -1}$, ${\displaystyle i}$ and ${\displaystyle -i}$, have each other as divisors. Gaussian integers with larger real or imaginary parts (or both) have at least 8 divisors. Given a Gaussian integer ${\displaystyle m+ni}$, a complete listing of its divisors includes at the very least the four complex units, the associates ${\displaystyle -m-ni}$, ${\displaystyle n-mi}$, ${\displaystyle -n+mi}$ and of course ${\displaystyle m+ni}$ itself. If these are the only divisors of that number, then it is a Gaussian prime.

The Gaussian integers form a unique factorization domain. Since multiplication is commutative in ${\displaystyle \mathbb {Z} [i]}$ (just as it is in ${\displaystyle \mathbb {Z} }$, and ${\displaystyle \mathbb {C} }$ for that matter), the order of the factors is irrelevant. Thus, ignoring the effect of the units, a Gaussian integer can be factored in only one way.

Theorem. Each Gaussian integer is the product of Gaussian primes having both real and imaginary part positive (and the appropriate complex unit if necessary) in only one way.

PROOF GOES HERE.

AT THIS POINT, SOME REMARKS ON THE FORMAT OF canonical prime factorizations OF GAUSSIAN INTEGERS WOULD BE APPROPRIATE.

We have established that multiplication of real numbers by other real numbers is exactly the same on the complex plane as on the real number line[2] and that ${\displaystyle \mathbb {Z} [i]}$ is an unique factorization domain just as ${\displaystyle \mathbb {Z} }$ is (by the fundamental theorem of arithmetic), but it would be a mistake to think that the factorizations of real numbers into real primes are always the same when those real primes are considered as Gaussian integers. In fact, there are numbers in ${\displaystyle \mathbb {Z} }$ which are not prime at all in ${\displaystyle \mathbb {Z} [i]}$. At this point we'll present and prove a fact about prime numbers in ${\displaystyle \mathbb {Z} }$ and then explain its relevance to Gaussian integers.

Theorem (Fermat). If a prime number ${\displaystyle p\in \mathbb {Z} ^{+}}$ is the sum of two perfect squares, then either that prime is 2 or that prime is one more than a multiple of 4. That is to say, if ${\displaystyle p=m^{2}+n^{2}}$ has a solution in integers, then ${\displaystyle p=2}$ or ${\displaystyle p\equiv 1\mod 4}$. Stated yet another way, given the function ${\displaystyle G_{c}(d)}$ from Waring's problem that gives the smallest number of ${\displaystyle c}$th powers to add up to ${\displaystyle d}$, we have ${\displaystyle G_{2}(p)=2}$ if ${\displaystyle p=2}$ or ${\displaystyle p\equiv 1\mod 4}$.

Proof. The case ${\displaystyle p=2}$ is disposed easily enough in proof by example: ${\displaystyle 2=1^{2}+1^{2}}$. We take it as axiomatic that all other prime numbers in ${\displaystyle \mathbb {Z} ^{+}}$ are odd. Therefore, two distinct squares are required, and furthermore, they must be of opposite parity: either ${\displaystyle m}$ is odd or ${\displaystyle n}$ is. Let's say ${\displaystyle m}$ is an even semiprime ${\displaystyle 2q}$ and therefore ${\displaystyle m\equiv 2\mod 4}$. Thus ${\displaystyle m^{2}=(2q)^{2}=4q^{2}\equiv 0\mod 4}$; that last congruence will of course also hold if ${\displaystyle m}$ is a multiple of 4 to begin with, so we can set it to the side for now. So, ${\displaystyle n}$ is odd, and there are two possibilities for its congruence to 4: ${\displaystyle n\equiv 1\mod 4}$ or ${\displaystyle n\equiv 3\mod 4}$. By modular arithmetic we see that ${\displaystyle 1\times 1=1\equiv 1\mod 4}$ and ${\displaystyle 3\times 3=9\equiv 1\mod 4}$ also. Therefore ${\displaystyle m^{2}+n^{2}\equiv 0+1=1\mod 4}$, as specified by the theorem.[3]

For example, ${\displaystyle 13=3\times 4+1=3^{2}+2^{2}}$ and ${\displaystyle 53=13\times 4+1=7^{2}+2^{2}}$.

It turns out that these are precisely the prime numbers of ${\displaystyle \mathbb {Z} }$ which are composite in ${\displaystyle \mathbb {Z} [i]}$. Also, if we know the solution to ${\displaystyle p=m^{2}+n^{2}}$, we actually also have two of the non-obvious divisors of that prime as a composite Gaussian integer.

Theorem. If a real prime number is the sum of two real perfect squares, then as a Gaussian integer it is actually composite, and those two real perfect squares form the real and the imaginary part respectively of some of that number's non-obvious divisors. This means that if ${\displaystyle p=m^{2}+n^{2}}$, then ${\displaystyle (m+ni)(m-ni)=p}$.

Proof. First let's remember the rule for complex multiplication: ${\displaystyle (a+bi)(c+di)=(ac-bd)+(ad+bc)i}$. Thus, to compute ${\displaystyle (m+ni)(m-ni)}$, we go: ${\displaystyle (mm-n(-n))+((-mn)+nm)=(m^{2}-n(-n))+(mn-mn)i=m^{2}+n^{2}+0i=p}$ as specified by the theorem. □

Going back to 13 and 53 from our previous examples, we see that ${\displaystyle (3+2i)(3-2i)=13}$ and ${\displaystyle (2+7i)(2-7i)=13}$. See A002144 for more examples of these primes that are composite as Gaussian integers. Also notice that ${\displaystyle (1+i)(1-i)=2}$.

Just for the sake of thoroughness, let's also consider cases where ${\displaystyle m=0}$. Clearly if ${\displaystyle n>1}$ then ${\displaystyle m^{2}+n^{2}}$ is a composite number in ${\displaystyle \mathbb {Z} }$. We no longer consider 1 a prime number, and application of the formula given above for divisors gives the rather uninteresting results ${\displaystyle (0+i)(0-i)=(1+0)(1-0)=1}$, which we already knew, once again confirming the removal of 1 from the list of prime numbers as correct.

A point that bears clarification, as it sometimes confuses students, is that while an integer may have one prime factorization in ${\displaystyle \mathbb {Z} }$ but another in ${\displaystyle \mathbb {Z} [i]}$, both of those domains are still unique factorization domains: the prime factorization in one of those domains is not a prime factorization in the other domain. Consider for example 4225, factored as ${\displaystyle 5^{2}\times 13^{2}}$ in ${\displaystyle \mathbb {Z} }$, but ${\displaystyle (1+2i)^{2}(2+i)^{2}(2+3i)^{2}(3+2i)^{2}}$ in ${\displaystyle \mathbb {Z} [i]}$. The ${\displaystyle 5^{2}\times 13^{2}}$ expression does not count as a prime factorization in ${\displaystyle \mathbb {Z} [i]}$ just as ${\displaystyle 25\times 169}$ does not count as a prime factorization in either domain; in both cases we're multiplying divisors that happen to be composite in the domain under consideration.

REMARKS ON MAPLE SUPPORT FOR GAUSSIAN INTEGERS GO HERE

Some number theoretic functions in Mathematica have a Boolean option GaussianIntegers which is set to False by default. For example, FactorInteger[13, GaussianIntegers -> True] would reveal divisors of 13 with a nonzero imaginar part, though this would be formatted closer to the canonical factorization format mentioned above than to the ${\displaystyle (m+ni)(m-ni)}$ form.

Although Mathematica will assume GaussianIntegers -> True on its own if the imaginary part of an argument to a relevant function is nonzero, it must be explicitly stated for purely real integers even if you actually type out + 0I (so PrimeQ[13 + 0I] would return True because the parser would disregard ${\displaystyle 0i}$ and the kernel would then regard 13 as an integer in ${\displaystyle \mathbb {Z} }$ rather than ${\displaystyle \mathbb {Z} [i]}$).

1. Bolker, p. 117. Technically the symbol is A(–1) as either the author or the editor or the typesetter have eschewed blackboard bold for most of the book save the list of errata.
2. Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications, 1969, reprinted 2007, 29 — 30. This is actually given as a second proof, simpler than the first, though here I have taken the liberty of fleshing out a few details glossed over by the book. However, the proof Bolker gives first is tremendously simple compared to one given at Planetmath, which manages to mention the rather simplifying question of parity but greatly complicating it.