Section 2.4 Number Theory
147
Finally we are ready to prove that the factorization of a composite number
n > 2 into prime factors is unique (save for ordering). If n is a composite number,
then n can be written as a product of primes:
n = p 1 p 2 g p r
where p 1 ≤ p 2 ≤ g ≤ p r and each p i is a prime number
Now suppose that n can also be written as
n = q 1 q 2 c q s
where q 1 ≤ q 2 ≤ g≤ q s and each q i is a prime number
Then
p 1 p 2 c p r = q 1 q 2 c q s
We are assuming that these two representations are different, but they might still
have some factors in common on both sides of the equation; let’s assume these
have been divided out. Then
p 1 0 p 1 p 2 c p r
so
p 1 0 q 1 q 2 c q s
By Practice 13, p 1 0 q i for some i, 1 ≤ i ≤ s. However, q i is a prime number, divisible only by itself and 1, which would mean that p 1 = q i . This is a contradiction
because we already eliminated common factors.
eXAMPLe 31
To find the unique factorization of 825 as a product of primes, we can start by
simply dividing 825 by successively larger primes (2, 3, 5, and so on).
2 | 825
825 = 3 # 275 = 3 # 5 # 55 = 3 # 5 # 5 # 11 = 3 # 5
2 # 11
Similarly,
455 = 5 # 7 # 13
From these factorizations we can see that gcd(825, 455) = 5. Decomposing two
positive integers into their respective prime number factorizations is another way
(besides the Euclidean algorithm) to determine their greatest common divisor.
PrACTiCe 14 Find the unique factorization of 1176 as a product of primes.
■
PrACTiCe 15 Find gcd(420, 66) by unique factorization into products of primes (see Example 27). ■
147
Finally we are ready to prove that the factorization of a composite number
n > 2 into prime factors is unique (save for ordering). If n is a composite number,
then n can be written as a product of primes:
n = p 1 p 2 g p r
where p 1 ≤ p 2 ≤ g ≤ p r and each p i is a prime number
Now suppose that n can also be written as
n = q 1 q 2 c q s
where q 1 ≤ q 2 ≤ g≤ q s and each q i is a prime number
Then
p 1 p 2 c p r = q 1 q 2 c q s
We are assuming that these two representations are different, but they might still
have some factors in common on both sides of the equation; let’s assume these
have been divided out. Then
p 1 0 p 1 p 2 c p r
so
p 1 0 q 1 q 2 c q s
By Practice 13, p 1 0 q i for some i, 1 ≤ i ≤ s. However, q i is a prime number, divisible only by itself and 1, which would mean that p 1 = q i . This is a contradiction
because we already eliminated common factors.
eXAMPLe 31
To find the unique factorization of 825 as a product of primes, we can start by
simply dividing 825 by successively larger primes (2, 3, 5, and so on).
2 | 825
825 = 3 # 275 = 3 # 5 # 55 = 3 # 5 # 5 # 11 = 3 # 5
2 # 11
Similarly,
455 = 5 # 7 # 13
From these factorizations we can see that gcd(825, 455) = 5. Decomposing two
positive integers into their respective prime number factorizations is another way
(besides the Euclidean algorithm) to determine their greatest common divisor.
PrACTiCe 14 Find the unique factorization of 1176 as a product of primes.
■
PrACTiCe 15 Find gcd(420, 66) by unique factorization into products of primes (see Example 27). ■