The Gaussian integers extend ordinary integers by adjoining i, but they retain enough Euclidean structure that gcds, factorisation and norm arguments remain algorithmic.
Write
Z[i]={a+bi : a,b in Z}.
The norm
N(a+bi)=a²+b²
turns two-dimensional arithmetic into an integer-valued size function. Because the norm is multiplicative and Euclidean division is possible by rounding to the nearest Gaussian integer, Z[i] is a Euclidean domain. That gives gcds, Bézout identities and unique factorisation up to units.
This is Guide 30 in the Bukit Timah Tutor Computational Number Theory series. It follows Guide 29 and prepares the norm-equation algorithms in Guide31.
1. Arithmetic in Z[i]
Add componentwise:
(a+bi)+(c+di)=(a+c)+(b+d)i.
Multiply using i²=−1:
(a+bi)(c+di)=(ac−bd)+(ad+bc)i.
Conjugation is
overline(a+bi)=a−bi.
The norm is the product with the conjugate:
N(z)=z overline(z)=a²+b².
2. Norm multiplicativity
For z,w in Z[i],
N(zw)=N(z)N(w).
This follows immediately from conjugation:
zw overline(zw)=z overline(z) w overline(w).
Norm multiplicativity lets integer factorisation constrain Gaussian factorisation. If z divides w in Z[i], then N(z) divides N(w) in Z.
3. Units
A Gaussian integer is a unit exactly when its norm is one.
The only solutions of
a²+b²=1
are
±1, ±i.
These four units create associates. For example, 2+i, −2−i, −1+2i and 1−2i differ by multiplication by units and represent the same irreducible factor up to association.
4. Divisibility
We say α divides β in Z[i] when β=αγ for some γ in Z[i].
For example,
(2+i)(3+2i)=4+7i.
Therefore 2+i divides 4+7i.
The norm confirms the possibility:
N(2+i)=5, N(4+7i)=65, 65/5=13.
5. Euclidean division by nearest Gaussian integer
Given α,β with β≠0, form the complex quotient α/β. Round its real and imaginary parts to nearest integers to obtain q in Z[i]. Set
r=α−qβ.
The geometry of the unit square ensures
N(r)<N(β).
Therefore repeated division terminates.
6. Worked Gaussian gcd
Take
α=4+7i, β=5−5i.
We know both were constructed to contain a common factor associated with 2+i, but suppose that is hidden.
The first Euclidean division uses quotient q=i:
α−iβ =(4+7i)−(5i+5) =−1+2i.
So
4+7i = i(5−5i)+(-1+2i).
The remainder has norm5, below N(β)=50.
7. Second Euclidean step
Now divide 5−5i by −1+2i. One nearest Gaussian quotient is
q=−3−i.
Then the remainder is zero:
5−5i = (−3−i)(−1+2i).
Therefore a Gaussian gcd is
gcd(4+7i,5−5i)=−1+2i
up to multiplication by a unit.
Its norm is five, so it is associated with 2+i.
8. Gaussian Bézout identities
Because the Euclidean algorithm works, extended Euclid works too. There exist A,B in Z[i] such that
Aα+Bβ=gcd(α,β).
The coefficient arithmetic is exactly the same recursive back-substitution used over ordinary integers.
This makes modular inversion possible in Gaussian quotient rings whenever the gcd is a unit.
9. Prime behaviour in Z[i]
Ordinary rational primes behave in three distinct ways.
Ramification:
2 = -i(1+i)².
Splitting: if p≡1 mod4, then
p=(a+bi)(a−bi)
for some integers a,b with p=a²+b².
Inertness: if p≡3 mod4, then p remains Gaussian prime.
10. Why p≡1 mod4 can split
For p≡1 mod4, Euler’s criterion shows that −1 is a quadratic residue modulo p.
So there exists r satisfying
r²≡−1 (mod p).
Then p divides
r²+1=(r+i)(r−i)
in Z[i], but p does not divide either factor as a Gaussian integer. Therefore p is reducible in Z[i].
A Gaussian gcd between p and r+i extracts one of the factors.
11. Construct 29 as a sum of two squares
Since 29≡1 mod4, find a square root of −1 modulo29.
One choice is
12²=144≡28≡−1 (mod29).
Compute
gcd_Z[i](29,12+i).
The Euclidean algorithm returns
5−2i
up to a unit.
Taking norms:
29=N(5−2i)=5²+2².
Thus
29=25+4.
12. The Euclidean steps for 29
First divide 29 by 12+i. A nearest quotient is2, giving
29−2(12+i)=5−2i.
Then
12+i=(2+i)(5−2i),
so the next remainder is zero.
The norm of the final nonzero remainder is29. This is exactly the desired representation.
13. Fermat’s two-square theorem
An odd prime p can be written as
p=a²+b²
if and only if
p≡1 (mod4).
The prime2 has the representation1²+1².
The Gaussian-integer proof explains both existence and uniqueness up to signs and swapping a,b.
14. General sums of two squares
A positive integer n is a sum of two squares exactly when every prime factor
q≡3 (mod4)
appears with even exponent in the prime factorisation of n.
This follows from Gaussian factorisation. Inert primes q≡3 mod4 can only contribute to a Gaussian norm in even total exponent.
15. Example: 65
Factor
65=5·13.
Both primes are1 mod4, so representations exist:
5=1²+2², 13=2²+3².
Using the Brahmagupta–Fibonacci identity,
(a²+b²)(c²+d²) =(ac−bd)²+(ad+bc)².
One representation is
65=(1·2−2·3)²+(1·3+2·2)² =(-4)²+7² =16+49.
So 65=4²+7².
16. The identity is just Gaussian multiplication
The two-square product identity is the norm of
(a+bi)(c+di).
The real part is ac−bd and the imaginary part is ad+bc.
Thus a classical integer identity is simply norm multiplicativity in Z[i].
17. Gaussian primes with nonzero imaginary part
If z=a+bi with both a and b nonzero, then z is Gaussian prime when N(z)=a²+b² is an ordinary rational prime.
For example,
2+i
has norm5, so it is Gaussian prime.
The converse needs care when z lies on an axis: a rational prime p≡3 mod4 is Gaussian prime even though its norm is p², not a rational prime.
18. Unique factorisation
Because Z[i] is Euclidean, it is a principal ideal domain and therefore a unique factorisation domain.
Every nonzero nonunit factors into Gaussian primes uniquely up to ordering and multiplication by units.
For example,
5=(2+i)(2−i) 13=(3+2i)(3−2i)
up to associates.
19. Modular arithmetic in Z[i]
One can compute modulo a Gaussian integer π just as over Z. If π is Gaussian prime, the quotient Z[i]/(π) is a finite field with N(π) elements.
For π=2+i, the quotient has5 elements.
This is another route to finite fields: instead of polynomial quotients over F_p, use quotient rings of algebraic-integer domains by prime ideals or prime elements.
20. Gaussian integers and quadratic residues
The condition p≡1 mod4 is equivalent to −1 being a square modulo p.
That modular square root supplies the input needed to split p in Z[i].
Thus Tonelli–Shanks from Guide5 can become the first stage of a constructive sum-of-two-squares algorithm.
21. Computational pipeline for p=a²+b²
For prime p≡1 mod4:
1. compute r with r²≡−1 mod p 2. compute gcd in Z[i] of p and r+i 3. let gcd=a+bi 4. verify a²+b²=p.
For the special norm x²+y², Cornacchia’s algorithm can perform the equivalent reconstruction using an ordinary integer Euclidean sequence. Guide31 develops that route and its generalisation x²+d y²=m.
22. Nearest-integer ambiguity
When α/β lies exactly on a boundary between nearest Gaussian integers, more than one quotient may satisfy the Euclidean remainder bound.
Different choices can produce different intermediate remainder sequences, but the final gcds differ only by units.
A reproducible implementation should specify its rounding convention.
23. Verification strategy
For each Euclidean division, verify
α=qβ+r
and
N(r)<N(β).
For a final gcd d, verify d divides both inputs and that the next remainder is zero.
For a sum-of-squares result, the strongest simple certificate is direct substitution:
a²+b² ?= n.
24. Common mistakes
1. Forgetting Gaussian units when comparing factors. 2. Treating ordinary absolute value rather than norm as the Euclidean measure. 3. Assuming every rational prime stays prime in Z[i]. 4. Claiming p≡1 mod4 is needed for composite n to be a sum of two squares.
5. Forgetting the special role of2. 6. Assuming norm primality is necessary for every Gaussian prime. 7. Rounding a complex quotient inconsistently. 8. Accepting a gcd representative without recognising associates.
25. Practice set
1. Multiply (2+i)(3+2i). 2. Compute N(4+7i). 3. List the four units. 4. Why is 2+i Gaussian prime?
5. Perform the first Euclidean step for 4+7i and 5−5i. 6. What gcd is obtained? 7. How are −1+2i and2+i related? 8. State the splitting rule for rational primes.
9. Verify 12²≡−1 mod29. 10. Compute gcd(29,12+i) in Z[i]. 11. Recover 29 as a sum of two squares. 12. State Fermat’s two-square theorem.
13. State the general criterion for n to be a sum of two squares. 14. Produce 65 as a sum of two squares. 15. Explain the two-square product identity using norms. 16. What does Z[i]/(2+i) contain?
26. Answers
1. 4+7i. 2. 65. 3. ±1,±i. 4. Its norm5 is rational prime.
5. Quotient i gives remainder −1+2i. 6. −1+2i up to a unit. 7. −1+2i=i(2+i). 8. 2 ramifies, p≡1 mod4 splits, p≡3 mod4 is inert.
9. 144≡28≡−1 mod29. 10. 5−2i up to a unit. 11. 29=5²+2². 12. Odd prime p is a sum of two squares iff p≡1 mod4.
13. Every prime q≡3 mod4 occurs to even exponent. 14. 65=4²+7². 15. It is N(zw)=N(z)N(w). 16. A finite field of five elements.
Sources and further study
Victor Shoup, A Computational Introduction to Number Theory and Algebra, develops Euclidean domains, finite fields and computational gcd ideas. Henri Cohen, A Course in Computational Algebraic Number Theory, provides the broader algorithmic-number-field setting for Euclidean algorithms, norms and ideal arithmetic.
Continue through Batch 08
Return to Guide 29. Continue to Guide 31: Cornacchia’s Algorithm and Guide 32: Higher Power Residues and Character Sums.