MAT315: Introduction to Number Theory
Lecture 2: Fundamental Theorem of Arithmetic and the
Gaussian Integers
Malors Emilio Espinosa Lara
September 12, 2023
University of Toronto
The Fundamental Theorem of
Arithmetic
Property of primes.
Theorem
Let p be a prime number and a, b integers. If p | ab, then p | a or p | b.
Proof.
If p doesn’t divide a, then gcd(a, p) = 1. Then there are integers x and y
with
ax + py = 1.
We multiply by b and we get
abx + pby = b.
Since ab is a multiple of p, the LHS is a sum of two multiples of p, so a
multiple of p itself. Hence, the RHS must be a multiple of p, i.e. p|b.
1
Generalization of the property.
Corollary
Let p be a prime number and a1, ..., an be integers. If p | a1a2...an, then
p|ai for some i = 1, ..., n.
Proof.
For clarity we just show it for n = 3. Suppose
p|abc.
By the previous theorem, p|a or p|bc. In the former case, we are done as
p|a. In the latter case, if p|bc then, once more by the previous theorem
p|b or p|c .
In any case, p divides one of a, b, c as desired.
2
Small numbers
We can now inspect the first few positive integers:
• 1 is a unit because (1)(1) = 1.
• 2 is a prime number because its only positive divisors are 1 and 2.
• 3 is a prime number because the only possible divisors are 1, 2, 3,
and 2 dosn’t work. Hence, its only divisors are 1, 3.
• 4 is a composite number because 4 = 2× 2. Furthermore, this is
the only possibility that works as 2× 2 = 4, 2× 3 = 6, 3× 3 = 9.
3
The Fundamental Theorem of Arithmetic
Theorem
Let n > 1 be an integer. Then it has a unique factorization into positive
prime numbers.
Proof.
Existence: We suppose we have the theorem proved up to the integer
n − 1. If n is prime we are done. Otherwise
n = ab,
with a < n, b < n. Concatenating their prime factorizations, we get one
for ab.
4
The Fundamental Theorem of Arithmetic
Theorem
Let n > 1 be an integer. Then it has a unique factorization into positive
prime numbers.
Proof.
Uniqueness: We suppose we have the theorem proved up to the integer
n − 1. Suppose n has two prime factorizations, say
pα11 p
α2
2 ... = q
β1
1 q
β2
2 ...
Since p1 | qβ11 qβ22 ... then, by the corollary, p1 divides one of q1, q2, ....
Since all are primes, we conclude WLOG p1 = q1. Hence
pα1−11 p
α2
2 ... = q
β1−1
1 q
β2
2 ...
This would be a smaller number than n with two different factorizations.
Contradiction!
5
The Gaussian Integers
Definition
Definition
A Gaussian Integer is a complex number a+ bi with a, b ∈ Z.
6
They form a grid
We can visualize them as forming a grid in the complex plane.
7
What made all work in Z?
What made all our work to function so far? That we were able to
divide one integer by another in a way that the residue strictly
decreased.
In the complex numbers we cannot decide consistently who is bigger or
smaller.
We try to fix this by working with the square of its distance to the origin
(because it is always a nonnegative integer!).
8
The norm and the circles
We define the norm of a Gaussian Integer as N(a+ bi) = a2 + b2.
9
Multiplicativity
Proposition
The norm is multiplicative, that is,
N((a+ bi)(x + yi)) = N(a+ bi)N(x + yi).
Proof.
Call z = x + yi . Then notice that
x2 + y2 = (x + yi)(x − yi) = zz = |z |2.
Then
N(zw) = |zw |2 = (|z ||w |)2 = |z |2|w |2 = N(z)N(w).
10
How do we use the norm?
The norm connects the multiplicative structure of the Gaussian Integers
with that of the regular integers.
For example, suppose uv = 1, with u, v in the Gaussian Integers. Now
take the norm! We get
N(u)N(v) = N(1) = 1.
Hence, units must have norm 1! There are only four Gaussian integers
of norm 1 and by inspection all of them are units. We get:
Proposition
The units of the Gaussian Integers are 1,−1, i ,−i
11
How do we use the norm?
This means that every Gaussian Integer z has associated to it 4 trivial
multiples: z ,−z , iz ,−iz . They form a square.
12
The grid of a number
The multiples form a grid of squares along the directions of the lines
through 0 and z , and the one 0 and iz .
13
The grid of a number
The fundamental square has side length |z |.
14
The grid of a number
Any Gaussian Integer is located in one of the squares (possibly in the
boundary).
15
The grid of a number
For every point in a square there is one corner at distance smaller than
the sidelength
16
Euclidean Algorithm
Theorem
Let w , z be Gaussian Integers with z ̸= 0. Then there are Gaussian
integers q, r such that
w = zq + r ,
and with 0 ≤ N(r) < N(z).
Proof.
1. Locate w in the appropriate square of the grid of multiples of z .
2. zq is one of the closest corners.
3. r is the vector from this corner to w .
4. Its norm decreases by the above property of the square.
17
Fundamental Theorem of Arithmetic
We now conclude, by the same process as for Z:
Theorem
Every Gaussian Integer that is not a unit has a unique prime factorization
up to units.