Page 292 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 271

First, we need to develop some results about divisibility.

LEMMA 2 If a, b, and c are positive integers such that gcd(a, b) = 1 and a | bc, then a | c.

Proof: Because gcd(a, b) = 1, by Bézout’s theorem there are integers s and t such that

sa + tb = 1.

Multiplying both sides of this equation by c, we obtain

sac + tbc = c.

We can now use Theorem 1 of Section 4.1 to show that a | c. By part (ii ) of that theorem, a | tbc.
Because a | sac and a | tbc, by part (i ) of that theorem, we conclude that a divides sac + tbc.
Because sac + tbc = c, we conclude that a | c, completing the proof.

We will use the following generalization of Lemma 2 in the proof of uniqueness of prime
factorizations. (The proof of Lemma 3 is left as Exercise 64 in Section 5.1, because it can be
most easily carried out using the method of mathematical induction, covered in that section.)

LEMMA 3 If p is a prime and p | a 1 a 2 ··· a n , where each a i is an integer, then p | a i for some i.

We can now show that a factorization of an integer into primes is unique. That is, we will
show that every integer can be written as the product of primes in nondecreasing order in at
most one way. This is part of the fundamental theorem of arithmetic. We will prove the other
part, that every integer has a factorization into primes, in Section 5.2.

Proof (of the uniqueness of the prime factorization of a positive integer): We will use a
proof by contradiction. Suppose that the positive integer n can be written as the product of primes
in two different ways, say, n = p 1 p 2 ··· p s and n = q 1 q 2 ··· q t , each p i and q j are primes such
that p 1 ≤ p 2 ≤ ··· ≤ p s and q 1 ≤ q 2 ≤ ··· ≤ q t .
When we remove all common primes from the two factorizations, we have

,
p ··· p i u
q ··· q j v
p i 1 i 2 = q j 1 j 2
where no prime occurs on both sides of this equation and u and v are positive integers. By
for some k. Because no prime divides another prime,
Lemma 3 it follows that p i 1 divides q j k
this is impossible. Consequently, there can be at most one factorization of n into primes in
nondecreasing order.
Lemma 2 can also be used to prove a result about dividing both sides of a congruence by
the same integer. We have shown (Theorem 5 in Section 4.1) that we can multiply both sides of
a congruence by the same integer. However, dividing both sides of a congruence by an integer
does not always produce a valid congruence, as Example 18 shows.

EXAMPLE 18 The congruence 14 ≡ 8 (mod 6) holds, but both sides of this congruence cannot be divided by 2
to produce a valid congruence because 14/2 = 7 and 8/2 = 4, but 7 ≡ 4 (mod 6). ▲