Gaussian Integers


Gaussian integers are complex numbers of the form

a+bi, a+bi,

where a a and b b are integers.

Like other complex numbers, Gaussian integers can be added, subtracted, and multiplied . For example:  Addition:(23i)+(4+5i)=6+2i, Subtraction:(23i)(4+5i)=28i,Multiplication:(23i)(4+5i)=8+10i12i15i2=232i. \begin{aligned} \text{ Addition:} & (2-3i)+(4+5i)=6+2i,\\ \text{ Subtraction:} & (2-3i)-(4+5i)=-2-8i,\\ \text{Multiplication:} & (2-3i)\cdot(4+5i) = 8+ 10i-12i-15i^2=23-2i. \end{aligned}

Here are some examples and properties of Gaussian integers:

  1. 23i,4+5i, 17, 0 2-3i, 4+5i, \ 17,\ 0 are all Gaussian integers, while 43 \frac{4}{3} , 2 \sqrt{2} , and 12+32i -\frac{1}{2}+\frac{\sqrt{3}}{2}i are not.

  2. The conjugate of a+bi a+bi is a+bi=abi \overline{a+bi}=a-bi , which is again a Gaussian integer.

  3. The norm of a+bi a+bi is N(a+bi)=(a+bi)(abi)=a2+b2 N(a+bi)=(a+bi)(a-bi)=a^2+b^2 , which is a non-negative integer.

  4. The absolute value of a Gaussian integer is the (positive) square root of its norm: a+bi=a2+b2 \lvert a+bi \rvert =\sqrt{a^2+b^2} .

  5. There are no positive or negative Gaussian integers and one cannot say that one is less than another. One can, however, compare their norms.

One of the most useful concepts for Gaussian integers is the norm

N(a+bi)=a2+b2. N(a+bi)=a^2+b^2.

The norm is always a non-negative integer, and is multiplicative (i.e., the norm of the product is the product of the norms). We say that a Gaussian integer zz is a unit if 1z\frac{1}{z} is also a Gaussian integer. A Gaussian integer (a+bi) (a+bi) is a multiple of Gaussian integer (c+di) (c+di) if

(a+bi)=(c+di)(e+fi) (a+bi)=(c+di)\cdot (e+fi)

for some Gaussian integer e+fi e+fi . In this case we say that c+di c+di divides a+bi a+bi, and use the notation

(c+di)(a+bi). (c+di) \mid (a+bi).

A Gaussian integer is called prime if it is not equal to a product of two non-unit Gaussian integers. Otherwise, it is called composite. Clearly, multiplying by a unit does not change primality. Note that a number may be prime as a usual integer, but composite as a Gaussian integer (for example 5=(2+i)(2i) 5=(2+i)(2-i)).

In the following sequence of theorems, we give a classification of Gaussian units and Gaussian primes.

Theorem 1. For a Gaussian integer z=(a+bi), z=(a+bi), the following three statements are equivalent:

1. z z is a unit, i.e. 1z \frac{1}{z} is a Gaussian integer.

2. N(z)=1 N(z)=1 .

3. z z is 1, 1, i, 1,\ -1,\ i, or i -i .

Proof. 1)2) 1)\Rightarrow 2) Suppose 1x=y \frac{1}{x}=y . Then 1=xy 1=xy , so N(1)=N(x)N(y) N(1)=N(x)N(y) . Since N(1)=1 N(1)=1 and N(x) N(x) and N(y) N(y) are integers, we have N(x)=1 N(x)=1 .

2)3) 2)\Rightarrow 3) We have

N(z)=N(a+bi)=a2+b2=1 N(z) = N(a+bi)=a^2+b^2 =1

for integers a a and b b . Then a2=1b21 a^2=1-b^2\leq 1 and, similarly, b21 b^2\leq 1 , implying one of aa or bb must be 11 and the other must be 00.

3)1) 3)\Rightarrow 1) This can be checked directly: 1±1=±1, 1±i=i. \frac{1}{\pm1}=\pm1,\ \frac{1}{\pm i}=\mp i. _\square

Now that we know all the units, we want to classify all Gaussian primes. Here is a first result in this direction.

Theorem 2. Suppose p=a+bi p=a+bi is a Gaussian prime and its norm a2+b2 a^2+b^2 is even. Then a2+b2=2 a^2+b^2=2 and p p , up to a unit, is 1+i 1+i .

Proof. Note that 2=(1+i)(1i) 2=(1+i)(1-i) . The integers a a and b b are either both even or both odd. In the first case, p p is divisible by 2 2 , which is divisible by (1+i) (1+i) . In the second case, p+(1+i) p+(1+i) is divisible by 2 2 . So in both cases p p is divisible by 1+i 1+i . Because p p is prime, it must equal e(1+i) e(1+i) , where e e is a unit. _\square

The following theorems are classical results from elementary number theory that are important for the theory of Gaussian integers. We will skip their proofs.

Theorem 3. Suppose p p is an odd prime. Then the congruence x2+10(modp) x^2+1 \equiv 0 \pmod p has a solution if and only if p1(mod4) p\equiv 1 \pmod 4 .


Theorem 4. (Fermat's Two-Square Theorem) An odd prime p p can be expressed as u2+v2 u^2+v^2 for integers u u and v v if and only if p1(mod4). p\equiv 1\pmod 4.

(Brahmagupta-Fibonacci Identity) Given two numbers, each of which can be written as the sum of two squares, their product can also be written as the sum of two squares. The identity is:

(a2+b2)(c2+d2)=(acbd)2+(ad+bc)2. (a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2.

The above theorems suggest the following:

Theorem 5.

a) If p=4k+1 p=4k+1 is a prime and p=u2+v2 p=u^2+v^2 , then u+vi u+vi and uvi u-vi are Gaussian primes.

b) If p=4k+3 p=4k+3 is a prime in N, {\mathbb N}, then it is a prime in Z[i] {\mathbb Z}[i] .

Proof. Recall that the norm of a product of two Gaussian integers equals the product of their norms.

a) The norm of u±vi u\pm vi is p p , so if u±vi u\pm vi is equal to a product of two Gaussian integers, one of the factors must have norm 1 1 , which makes it a unit.

b) If p=4k+3 p=4k+3 is a product of non-unit Gaussian integers, then, because its norm is p2 p^2 , the factors must have norm p p . This is impossible by Theorem 4. _\square

Finally, we give a proof of the classification of Gaussian primes based on the uniqueness of prime factorization of Gaussian integers. Another, self-contained proof is given in the Worked Examples.

Theorem 6. (Classification of Gaussian Primes) All Gaussian primes are those described in Theorem 5.

Proof. Suppose a+bi a+bi is a Gaussian prime. Consider

a2+b2=(a+bi)(abi). a^2+b^2=(a+bi)(a-bi).

We can decompose a2+b2a^2+b^2 into a product of usual primes. Then for the prime 2 2 , write 2=(1+i)(1i) 2=(1+i)(1-i) and for the primes p=4k+1 p=4k+1 write p=(u+vi)(uvi) p=(u+vi)(u-vi) . Because of the uniqueness of the decomposition into a product of primes, a+bi a+bi must be one of the primes defined above, proving the theorem.

Worked Examples

1. Find all Gaussian primes with norm up to 20. 20.

Solution: By the classification, up to units, 1+i 1+i is the only Gaussian prime with norm 2 2 . If pp is prime of the form p=4k+3 p=4k+3 , the norm is p2 p^2 , so we must have p=3 p=3 . For primes p=4k+1, p=4k+1, p p is 5,13, 5,13, or 1717 . Note that 5=22+12, 5=2^2+1^2, 13=32+22 13=3^2+2^2 , and 17=42+12 17=4^2+1^2 . Therefore, the Gaussian primes with norm up to 20 20 are, in increasing order of norm:

1+i,2+i,2i,3,3+2i,32i,4+i,4i. 1+i, 2+i, 2-i, 3, 3+2i, 3-2i, 4+i, 4-i.

2. Suppose a+bi a+bi is a Gaussian integer and suppose p=4k+3 p=4k+3 divides a2+b2 a^2+b^2 . Show pa+bi p|a+bi .

Solution: If b0(modp), b\neq 0 \pmod p, then consider xab(modp) x\equiv \frac{a}{b} \pmod p . We have x2+1=a2+b2b20(modp) x^2+1=\frac{a^2+b^2}{b^2} \equiv 0 \pmod p . From Theorem 3, this is impossible. So pb p|b , implying pa2 p|a^2 and pa p|a . Therefore, pa+bi. p|a+bi.

3. Suppose a+bi a+bi is a Gaussian integer, and p=4k+1 p=4k+1 divides a2+b2 a^2+b^2 . Suppose p=u2+v2. p=u^2+v^2. Show that either u+via+bi u+vi|a+bi or uvia+bi u-vi|a+bi (or both).

Solution: Note that p=(u+vi)(uvi) p=(u+vi)(u-vi) . If pb p|b , then, as in the Example 2, pa+bi p|a+bi , so both u+vi u+vi and uvi u-vi divide a+bi. a+bi. If b0(modp), b\neq 0 \pmod p, consider an integer c c such that abc(modp) \frac{a}{b}\equiv c \pmod p . Then c2+10(modp) c^2+1\equiv 0 \pmod p . Similarly, uvx(modp) \frac{u}{v}\equiv x \pmod p for some integer x x . Because

(xc)(x+c)=x2c20(modp), (x-c)(x+c)=x^2-c^2 \equiv 0\pmod p,

either cx(modp) c\equiv x \pmod p or cx(modp) c\equiv -x \pmod p . In the first case, for an integer kbv(modp), k\equiv \frac{b}{v} \pmod p, we have bkv(modp) b\equiv kv \pmod p and aku(modp) a\equiv ku\pmod p . So (a+bi)k(u+vi) (a+bi)-k(u+vi) is a multiple of p p , so a+bi a+bi is a multiple of u+vi u+vi . Similarly, in the second case a+bi a+bi is a multiple of uvi. u-vi.

4. Show that all Gaussian primes are among those described in Theorem 2 and Theorem 5.

Solution: Suppose a+bi a+bi is a Gaussian prime, and N N is its norm. Because it is not zero and not a unit, N2 N\geq 2 . From Theorem 2, Example 2 and Example 3, a+bi a+bi is a multiple of one of the known Gaussian primes. Because a+bi a+bi is a prime, the ratio must be a unit, which implies the result.

The Fundamental Theorem of Arithmetic states that every positive integer can be uniquely expressed as a product of positive primes, up to the order of multiplication. Can we create a system where it is not true?

Example. Consider the set N1 \mathbb{N}_{1} of all positive integers of the form 4k+1 4k+1 , where k k is a positive integer. A product of any two such integers in N1 \mathbb{N}_1 is again an integer of this form. We will call an integer from N1 \mathbb{N}_1 prime if it is not a product of two smaller integers from N1 \mathbb{N}_{1} , and the integer is called composite otherwise. By definition, every integer from N1 \mathbb{N}_{1} is a product of primes from N1 \mathbb{N}_1 . However, the product may not be uniquely expressed. For example, we can see that 9,21,49 9, 21, 49 are all primes in N1 \mathbb{N}_1 , and we have 441=949=2121 441 = 9 \cdot 49 = 21 \cdot 21 .

Of course, N1 \mathbb{N}_1 is very different from integers or natural numbers, but this showcases the fact that there must be a reason for why the prime decomposition is unique. The deep reason is the existence of the division algorithm that produces a remainder that is strictly smaller than the divisor. Interestingly, the same property holds for the Gaussian integers, with respect to the norm:

Lemma 1. (Division algorithm) Suppose x x and y y are Gaussian integers, y0 y\neq 0 . Then there exist Gaussian integers z z and r r such that x=yz+r x=yz+r and r<y. |r|<|y|.

Proof. Dividing x x by y y , we get a number a+bi a+bi where a a and b b are rational (not necessarily integers). Suppose n n is the closest integer to a a and m m is the closest integer to b b . Denote z=n+mi z=n+mi . Then xyz=(an)+(mb)i(12)2+(12)2=12<1. |\frac{x}{y}-z|= |(a-n)+(m-b)i| \leq \sqrt{(\frac{1}{2})^2+ (\frac{1}{2})^2}=\frac{1}{\sqrt{2}}<1. So if r=xyz, r=x-yz, then r=yxyz<y. |r|=|y|\cdot |\frac{x}{y}-z|<|y|. _ \square

This property is called the Euclidean domain property. In fact, in every Euclidean domain the factorization into a product of primes is unique. We present an argument for the Gaussian integers, which can be easily adapted for the regular integers. The following lemma is needed in the proof, and is known as Euclid's Lemma when restricted to integers.

Lemma 2. Suppose p p is a prime Gaussian integer and p p divides uv, uv, for some Gaussian integers u u and v v . Then pu p|u or pv p|v .

Proof. Consider the set I I of all Gaussian integers of the form yu+zp yu+zp for arbitrary Gaussian integers y y and z z . This is also known as the ideal generated by u u and p p . It has the property that any sum or difference of two elements from I I is in I I , and any Gaussian integral multiple of an element from I I is in I I . Suppose a a is the element of I I with the smallest possible non-zero absolute value. From Lemma 1, every element of I I is a multiple of a a , otherwise the non-zero remainder, which also lies in I I , will have a smaller absolute value. In particular, ap a|p . Because p p is prime, either pa \frac{p}{a} is a unit or a a is a unit. In the first case, u u is a multiple of a a , so it is a multiple of p p . In the second case, multiplying a a by 1a \frac{1}{a} , we express 1 1 as yu+zp yu+zp . Multiplying by v v , we get v=y(uv)+zvp v=y(uv)+zvp . Because puv, p|uv, this implies that pv p|v . _ \square

Theorem 1. (Unique Factorization Property) Every non-zero Gaussian integer can be uniquely expressed as a product of Gaussian primes, up to ordering and multiplication by units.

Proof. First we prove that a factorization into a product of primes always exists. If not, take x x to be the Gaussian integer with smallest absolute value which is not a product of primes. Then x x is not a prime, so x=x1x2, x=x_1x_2, a product of two non-zero, non-unit Gaussian integers. Since norms are multiplicative and positive integers, x1,x2 x_1, x_2 must have smaller norm than x x , so they are both products of primes. If so, x=x1x2 x= x_1 x_2 is also the product of primes, hence a contradiction.

Now we will prove the uniqueness. Suppose that x x is the Gaussian integer with smallest norm that admits two substantially different decompositions into a product of primes:

x=p1p2ps=q1q2qt. x=p_1p_2 \ldots p_s=q_1q_2 \ldots q_t.

Applying lemma 2 to p=p1 p=p_1 , u=q1 u=q_1 , v=q2...qt v=q_2...q_t we get that either p1q1 p_1|q_1 or p1q2...qt p_1|q_2...q_t . In the second case we apply it again, and again... as a result we get that p1 p_1 must divide qk q_k for some k k . Because the number qk q_k is prime, this means that qk q_k is up to a unit p1 p_1 . Then we can cancel them out, and get a new x, x, with two different prime decompositions and smaller norm. This contradicts our choice of x x . _ \square

Another property of the Euclidean domain, very much related to the Unique Decomposition, is the existence of the Euclidean Algorithm for finding the greatest common divisor. This algorithm, as well as the uniqueness of prime decomposition for the usual integers goes all the way back to Euclid's Elements!

The Euclidean Algorithm works as follows: Suppose x x and y y are (Gaussian) integers. We order the pair (x,y), (x,y), so that N(x)N(y) N(x)\geq N(y) and call it (x0,y0) (x_0,y_0) . Then we use it to get new pairs, (x1,y1), (x2,y2),... (x_1,y_1),\ (x_2,y_2),... as follows. At every step, we divide xi x_i by yi y_i . If the remainder is zero, we stop, and claim that yi y_i the greatest common divisor of x x and y y , denoted gcd(x,y) \gcd(x,y) . If there is a non-zero remainder, i.e. xi=yizi+ri, x_i=y_iz_i+r_i, we take (xi+1,yi+1)=(yi,ri) (x_{i+1},y_{i+1})=(y_i,r_i) and continue.

Theorem 2.

1) For every initial pair (x,y) (x,y) , the Euclidean algorithm terminates after a finite number of steps.

2) The number gcd(x,y) \gcd(x,y) divides both x x and y y , and every (Gaussian) integer d d that divides both x x and y y must divide gcd(x,y) \gcd (x,y) .

Proof. 1) For the Gaussian integers, note that N(yi+1)=N(ri)<N(yi) N(y_{i+1})=N(r_i)<N(y_{i}) , and the norm, being a positive integer, cannot decrease indefinitely.

Proof. 2) Suppose gcd(x,y)=yi \gcd(x,y)=y_i . Then it clearly divides xi x_i and yi y_i . Because yi1=xi y_{i-1}=x_i and xi1=yi1zi1+ri1=xizi1+yi, x_{i-1}=y_{i-1}z_{i-1}+r_{i-1}=x_iz_{i-1}+y_i, it divides xi1 x_{i-1} and yi1 y_{i-1} . Continuing in this manner, we prove that gcd(x,y) \gcd(x,y) divides x x and y y .

If d d divides both x=x0 x=x_0 and y0 y_0 , then it divides x1=y0 x_1=y_0 and y1=x0y0z0 y_1=x_0-y_0z_0 . Continuing in this manner, we prove that d d divides yi=gcd(x,y) y_i=\gcd(x,y) . _\square

We finish this post by reproducing one of the recent proofs of the Fermat Two Squares Theorem, due to Don Zagier. An involution is such map ϕ \phi from a set to itself, that ϕ(ϕ(x))=x \phi(\phi(x))=x for all elements x x .

Don Zagier's One-Sentence Proof of Fermat Two Squares Theorem. (Amer. Math. Monthly 97 (1990), no. 2, 144).

The involution on the finite set S={(x,y,z)N3:x2+4yz=p} S=\{(x,y,z)\in {\mathbb N}^3: x^2+4yz=p\} defined by

(x,y,z){(x+2z,z,yxz),if x<yz(2yx,y,xy+z),if yz<x<2y(x2y,xy+z,y),if x>2y (x,y,z) \rightarrow \begin{cases} (x+2z,z,y-x-z), & \text{if } x < y-z\\ (2y-x,y,x-y+z),& \text{if } y-z < x < 2y\\ (x-2y,x-y+z,y), & \text{if } x > 2y \\ \end{cases}

has exactly one fixed point, so S |S| is odd and the involution defined by (x,y,z)(x,z,y) (x, y, z) \to (x, z, y) also has a fixed point. _\square

Note by Calvin Lin
7 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

here 0 can't be written as product of complex numbers so is 0 a prime

I know you will argue that 0 has infinite divisors so it is neither prime nor composite , by using theorem 4 what are the 2 Gaussian primes such that their product is zero ( her we shall not take ( 0 + 0i and 0 - 0i)

U Z - 6 years, 7 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...