HIGHER

MATH
CLUB
10. Prime Factorization
Mathematician of the week: Ernst Kummer
• Ernst Kummer (1810-1893) was a
mathematician who is famous for his
contributions in number theory.
• Using the ideas of prime factorization, he
came up with “ideal numbers”, which were
later formalized by Dedekind into ideals.
• Using this, he proved many cases of
Fermat’s Last Theorem.
Guiding Question
• It is well-known that any positive integer can be uniquely
written (up to permutation) as a product of primes :
𝑛 = 𝑝! 𝑝" … 𝑝# .

• Does a similar phenomenon hold in other rings?

Irreducibles
• We first generalize the notion of a prime.
• Let 𝑅 be an integral domain. An element 𝑝 ∈ 𝑅 is irreducible
iff it is nonzero, not a unit, and if 𝑝 = 𝑎𝑏 for 𝑎, 𝑏 ∈ 𝑅, then
one of 𝑎, 𝑏 is a unit. (The other one is associates with 𝑝.)
• The term prime is used for another definition – more on this later.
• For instance, in ℤ, the irreducibles are the usual primes and
also the negatives of primes. In ℝ 𝑥 , linear polynomials are
irreducible.
Unique Factorization Domains
• We now state unique factorization:
• Any nonzero 𝑛 ∈ 𝑅 can be written as
𝑛 = 𝑢𝑝! 𝑝" … 𝑝# ,
where 𝑢 is a unit and the 𝑝$ are irreducible. Moreover, suppose that
𝑛 = 𝑣𝑞! 𝑞" … 𝑞% ,
where 𝑣 is a unit and the 𝑞$ are irreducible. Then 𝑘 = 𝑙, and we can
rearrange 𝑞! , 𝑞" , … , 𝑞# into 𝑞&! , 𝑞&" , … , 𝑞&# such that 𝑝$ and 𝑞&$ are
associates for all 𝑖.
Unique Factorization Domains
• However, it turns out that this is not always true!
• Consider the ring ℤ −3 = 𝑎 + 𝑏 −3 ∶ 𝑎, 𝑏 ∈ ℤ .
(If you don’t like irrational numbers, you can define this ring as a quotient: ℤ 𝑥 / 𝑥 ! + 3 .)
• In general, ℤ 𝛼 and ℚ 𝛼 mean the smallest ring and smallest
field containing 𝛼, respectively.
• The elements 2, 1 + −3, 1 − −3 are irreducible. (Why?)
However, 4 = 2 ∗ 2 = 1 + −3 1 − −3 .
Unique Factorization Domains
• If a ring has unique factorization, we say that it is a unique
factorization domain, or UFD. (So ℤ −3 is not a UFD.)
• The main goal becomes: how do we prove that some rings
are UFDs? (How do we even prove it in ℤ?)
ℤ is a UFD
Euclid’s Lemma
• Unique factorization consists of two parts: existence of a
factorization, and uniqueness of that factorization.
• Existence aside, to prove uniqueness we need the following:
• Euclid’s Lemma. Let 𝑝 be any irreducible element. Then if
𝑝 ∣ 𝑎𝑏, then 𝑝 ∣ 𝑎 or 𝑝 ∣ 𝑏.
• An element 𝑝 satisfying the above condition is called prime. Thus,
Euclid’s Lemma states that every irreducible element is prime.
Euclid’s Lemma
• The uniqueness part of unique factorization follows from
Euclid’s Lemma.
• To prove this, induct on the length max 𝑘, 𝑙 .
• If 𝑢𝑝! 𝑝" … 𝑝# = 𝑣𝑞! 𝑞" … 𝑞$ , where WLOG 𝑘 ≥ 𝑙, then 𝑝#
divides at least one of 𝑣, 𝑞! , 𝑞" , … , 𝑞$ . 𝑝# can’t divide 𝑣, so
suppose that 𝑝# ∣ 𝑞% . Hence, 𝑝# , 𝑞% are associates.
• We divide both sides by 𝑝# and induct down. (The base case is trivial.)
Principal Ideal Domains
• In a ring, an ideal of the form 𝑛 is called principal.
• An integral domain 𝑅 is a principal ideal domain, or PID, iff all
ideals of 𝑅 are principal.
• Proposition. If 𝑅 is a PID, then Euclid’s Lemma holds.
• Proof. Suppose that 𝑝 is irreducible and 𝑝 ∣ 𝑎𝑏. First consider
the ideal 𝑝, 𝑎 . Since 𝑅 is a PID, let 𝑝, 𝑎 = 𝑐 .
• Since 𝑝, 𝑎 ∈ 𝑐 , 𝑐 divides 𝑝 and 𝑎.
Principal Ideal Domains
• Proposition. If 𝑅 is a PID, then Euclid’s Lemma holds.
• Since 𝑝 is irreducible, either 𝑐 and 𝑝 are associates, or 𝑐 is a
unit. In the former case, we get 𝑝 ∣ 𝑎, so we are done.
• If 𝑐 is a unit, then 1 ∈ 𝑝, 𝑎 . Let 𝑝𝑥 + 𝑎𝑦 = 1. Thus:
𝑝 ∗ 𝑏𝑥 + 𝑎𝑏 ∗ 𝑦 = 𝑏.
• Therefore, 𝑏 is a multiple of 𝑝, so we are done once more.
Q.E.D.
Principal Ideal Domains
• PIDs satisfy the existence part of unique factorization as well!
• Theorem. If 𝑅 is a PID, then 𝑅 is a UFD.
• Proof. Let 𝑛& ∈ 𝑅 be nonzero, and suppose that 𝑛& cannot be
factored into irreducibles.
• 𝑛& must not be a unit or irreducible, so we write 𝑛& = 𝑎& 𝑏& ,
where 𝑎& , 𝑏& are not units. 𝑎& and 𝑏& cannot both be
factorable, so WLOG assume that 𝑎& cannot be factored.
Principal Ideal Domains
• Theorem. If 𝑅 is a PID, then 𝑅 is a UFD.
• Let 𝑛! = 𝑎& , and repeat the process: write 𝑛! = 𝑎! 𝑏! , and
WLOG, 𝑎! can’t be factored, so let 𝑛" = 𝑎! , etc.
• We get an infinite sequence 𝑛& , 𝑛! , 𝑛" , …. If we look at the
ideals, we have an ascending chain:
𝑛& ⊊ 𝑛! ⊊ 𝑛" ⊊ ⋯ .
Principal Ideal Domains
• Theorem. If 𝑅 is a PID, then 𝑅 is a UFD.
• We take the union of all the ideals 𝑛% . This is also an ideal
of 𝑅. (Why?) Let this ideal be 𝑚 .
• Since 𝑚 ∈ ⋃ 𝑛% , we must have 𝑚 ∈ 𝑛' for some 𝐾. But
this implies that 𝑚 ⊆ 𝑛' ⊊ 𝑛'(! ⊆ 𝑚 .
• Contradiction!
Q.E.D.
Principal Ideal Domains
• Although all PIDs are UFDs, the converse is false.
• For instance, ℤ 𝑥 is not a PID (why?), but it is a UFD.
• The existence part is easy, but Euclid’s Lemma is quite hard
to prove and requires something called Gauss’ Lemma.
Euclidean Domains
• So how do we prove that an integral domain 𝑅 is a PID?
• A function 𝑁: 𝑅 ∖ 0 → ℕ& is a Euclidean norm on 𝑅, iff for
any nonzero 𝑎, 𝑏, there exist 𝑞, 𝑟 such that 𝑎 = 𝑏𝑞 + 𝑟, and
either 𝑟 = 0 or 𝑁 𝑟 < 𝑁 𝑏 .
• 𝑅 is Euclidean iff there is a Euclidean norm on 𝑅.
• It’s called that because we can perform the Euclidean Algorithm.
Euclidean Domains
• Theorem. If 𝑅 is a Euclidean domain, then 𝑅 is a PID.
• Proof. Let 𝐼 be an ideal of 𝑅. If 𝐼 = 0 = 0 then we are
done, otherwise let 𝑏 be the element in 𝐼 ∖ 0 with the
smallest norm 𝑁 𝑏 . We show that 𝐼 = 𝑏 .
• This is equivalent to showing that every element of 𝐼 is a
multiple of 𝑏.
Euclidean Domains
• Theorem. If 𝑅 is a Euclidean domain, then 𝑅 is a PID.
• For any nonzero 𝑎 ∈ 𝐼, let 𝑎 = 𝑏𝑞 + 𝑟 such that 𝑟 = 0 or
𝑁 𝑟 < 𝑁 𝑏 . We desire that 𝑟 = 0.
• Suppose that 𝑟 ≠ 0 and 𝑁 𝑟 < 𝑁 𝑏 . But by definition,
𝑟 = 𝑎 − 𝑏𝑞 ∈ 𝐼, so this contradicts the definition of 𝑏.
Q.E.D.
Euclidean Domains
• The following are Euclidean norms:
• On ℤ: 𝑁 𝑎 = 𝑎 ;
• On ℤ 𝑖 : 𝑁 𝑎 + 𝑏𝑖 = 𝑎" + 𝑏 " ;
• On 𝐹 𝑥 (where 𝐹 is a field): 𝑁 𝑓 = deg 𝑓.
• Therefore, those rings are all PIDs and hence UFDs.
)!( )!*
• Not all PIDs are Euclidean: ℤ is an example.
"
Gaussian Integers
• We prove that 𝑁 𝑎 + 𝑏𝑖 = 𝑎" + 𝑏 " is Euclidean on ℤ 𝑖 .
• Let 𝛼, 𝛽 be nonzero Gaussian integers. To perform “division”
and write 𝛼 = 𝛽𝜒 + 𝜌 for 𝜌 “smaller” than 𝛽, the idea is to
+
find , and then round the real and imaginary parts.
,
• Let 𝛼 = 𝑎 + 𝑏𝑖 and 𝛽 = 𝑐 + 𝑑𝑖.
𝛼 𝛼 𝛽̅ 𝑎𝑐 + 𝑏𝑑 𝑏𝑐 − 𝑎𝑑
= = " "
+ " "
𝑖
𝛽 𝑁 𝛽 𝑐 +𝑑 𝑐 +𝑑
Gaussian Integers
• Let 𝑎𝑐 + 𝑏𝑑 = 𝑐 " + 𝑑" 𝑥 + 𝑟; 𝑏𝑐 − 𝑎𝑑 = 𝑐 " + 𝑑" 𝑦 + 𝑠;
such that − 𝑐 " + 𝑑" ≤ 2𝑟, 2𝑠 ≤ 𝑐 " + 𝑑" .
• Let 𝜒 = 𝑥 + 𝑦𝑖 and 𝜌 = 𝛼 − 𝛽𝜒.
̅ = 𝑟 + 𝑠𝑖, so that
• Verify that 𝛽𝜌
𝑁 𝛽̅ 𝑁 𝜌 = 𝑟 " + 𝑠 " < 𝑐 " + 𝑑" "
= 𝑁 𝛽̅ 𝑁 𝛽 .
• Therefore, 𝑁 𝜌 < 𝑁 𝛽 , and we are done.
Q.E.D.
Gaussian Integers
• The technique of dividing in ℚ 𝑑 and rounding works to
prove that ℤ 𝑑 is a UFD for 𝑑 = −2, −1,2,3.
• With slight modifications, it can be used to show the cases
𝑑 = 6,7 as well.
• For larger values of 𝑑, see Exercise #5.
Difficult results
• Let 𝑑 ≠ 0,1 be square-free, and define 𝒪ℚ . to be ℤ 𝑑 if
!( .
𝑑 ≡ 2,3 mod 4, and ℤ if 𝑑 ≡ 1 mod 4.
"
• Mathematicians usually prefer this ring to ℤ 𝑑.
• Define the standard norm to be: 𝑁 𝑎 + 𝑏 𝑑 = 𝑎" − 𝑑𝑏 " .
This is not necessarily Euclidean. If it is, we say the ring in
question is norm-Euclidean.
Difficult results
• 𝒪ℚ . is a UFD iff it is a PID. (This one isn’t too hard.)
• Let 𝑑 > 0 be square-free, then 𝒪ℚ ). is a UFD iff 𝑑 is one
of nine Heegner numbers: 1, 2, 3, 7, 11, 19, 43, 67, 163.
• These numbers are linked to many other fields of math, and are
responsible for the magical identity
𝑒 , !-. ≈ 640320. + 744 − 0.00000000000075.
Difficult results
• Let 𝑑 ≠ 0,1 be square-free, then 𝒪ℚ . is norm-Euclidean
iff 𝑑 is among the following numbers: −11, −7, −3, −2, −1,
2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73.
• If 𝑑 = 14, 22, 23, 31, 38, 43, 46, 47, 53, 59, 61, 62, 67, etc.,
then 𝒪ℚ . is Euclidean but not norm-Euclidean.
• The norm function can be very complicated, and only non-
constructive proofs are known for most of these rings.
Difficult results
• Assume the Generalized Riemann Hypothesis. For 𝑑 > 0
squarefree, 𝒪ℚ . is a UFD iff it is Euclidean.
• Without GRH, there are at most 2 exceptions, which must be at
least 127. (None have been found so far.)
• Are there infinitely many 𝑑 > 0 such that 𝒪ℚ . is a UFD?
Nobody knows. This is the class number 1 problem.
A story on ideals
• In 1637, Pierre de Fermat claimed to have proven that 𝑎! + 𝑏 ! = 𝑐 ! has no
solutions in positive integers for 𝑛 > 2, but provided no proof. Fermat and Euler
proved the cases 𝑛 = 4 and 𝑛 = 3, respectively.
• In 1847, Gabriel Lamé published a proof of Fermat’s Last Theorem. It suffices to
consider the case where 𝑛 ≥ 5 is an odd prime. He factored:
𝑎! + 𝑏 ! = 𝑎 + 𝑏 𝑎 + 𝜁! 𝑏 𝑎 + 𝜁!"𝑏 ⋯ 𝑎 + 𝜁!!#$𝑏 ,
"% "%
where 𝜁! = cos !
+ 𝑖 sin !
, and then derived a contradiction from there.
• Unfortunately, this proof is wrong, because it implicitly assumes that ℤ 𝜁! is a
UFD for 𝑛 an odd prime (which is false for 𝑛 ≥ 23).
A story on ideals
• The same year, Ernst Kummer was also studying unique factorization. He tried to
salvage unique factorization in ℤ 𝜁! by adding new “numbers” to the ring, called
ideal numbers. In 1850, Kummer used this to prove certain cases of FLT.
• In 1876, Richard Dedekind realized that this theory of ideal numbers can be
simplified to the theory of ideals. For a certain kind of ring called a Dedekind
domain (which includes 𝒪ℚ ' ), we can factor the ideals into primes!
• An ideal 𝐼 is prime iff 𝑎𝑏 ∈ 𝐼 implies 𝑎 ∈ 𝐼 or 𝑏 ∈ 𝐼. So naturally, they defined an
element 𝑝 to be prime iff 𝑝 is prime. Later, elements that can’t factor were
called irreducible, since the name “prime” was already taken.
Exercises
Note: citing the “Difficult results” slides is NOT allowed.
1. Prove that in an integral domain, any prime element is irreducible.
2. Let 𝑑 ≠ 0,1 be square-free. Prove that if (a) 𝑑 ≤ −3, or (b) 𝑑 ≡ 1 mod 4, then
ℤ 𝑑 is not a UFD.
3. Let 𝐹 be a field. Prove that 𝐹 𝑥 is Euclidean (and hence, a UFD).
4. Solve the equation 𝑥 " + 2 = 𝑦 ( over the integers.
(Hint: factor as 𝑥 + −2 𝑥 − −2 = 𝑦 !. You may assume without proof that ℤ −2 is a UFD.)

5. Let 𝑑 ≠ 0,1 be square-free. Prove that ℤ 𝑑 is norm-Euclidean iff the planar

region defined by −1 < 𝑥 " − 𝑑𝑦 " < 1 can be translated by a vector in ℤ" to
cover any point in ℚ".