146
Proofs, Induction, and Number Theory
Recall that a prime number is an integer p > 1 that is not divisible by any
integers other than 1 and p. If a is an integer that is a multiple of a prime p,
then clearly p 0 p and p 0 a, so gcd(a, p) = p. But if a is not a multiple of p, then
gcd(a, p) = 1 because nothing else divides p. Therefore all integers are either
multiples of p or are relatively prime to p.
Suppose that p is a prime number that divides the product ab of integers a and b.
Because p is “irreducible,” p must divide either a or b. More formally, if p does not
divide a, that is, a is not a multiple of p, then a is relatively prime to p, gcd(a, p) = 1,
and there exist integers i and j such that
1 = ia + jp
Multiplying this equation by b,
b = (ia)b + ( jp)b = i (ab) + ( jp)b
Because p 0 ab, ab can be written as kp, where k is an integer, so the previous
equation becomes
b = i(kp) + ( jp)b = (ik + jb)p
ik + jb an integer
so that p 0 b. This proves the following theorem.
tHeoReM oN DIvISIoN by PrIME NuMbErS
Let p be a prime number such that p 0 ab where a and b are integers. Then either
p 0 a or p 0 b.
PrACTiCe 11
a. Prove that if d is a positive integer such that d 0 a and d 0 b, then d 0 c, where c = ia + jb.
b. Prove that if d 0 c, then c ≥ d.
■
PrACTiCe 12 The integers 21 and 16 are relatively prime. Find i and j such that i (21) + j(16) = 1. ■
PrACTiCe 13 Extend the theorem on division by prime numbers as follows: Let p be a prime number such that p 0 a 1 a 2 … a k where each a i is an integer. Then p 0 a j for some j, 1 ≤ j ≤ k.
(Hint: You want to prove that this is true for every positive integer k—What proof technique
should you use?)
■
DeFinition rElaTIvEly PrIME
Two integers a and b are relatively prime if gcd(a, b) = 1.
From the theorem on gcd(a, b), it follows that a and b are relatively prime if
and only if there exist integers i and j such that
ia + jb = 1
Proofs, Induction, and Number Theory
Recall that a prime number is an integer p > 1 that is not divisible by any
integers other than 1 and p. If a is an integer that is a multiple of a prime p,
then clearly p 0 p and p 0 a, so gcd(a, p) = p. But if a is not a multiple of p, then
gcd(a, p) = 1 because nothing else divides p. Therefore all integers are either
multiples of p or are relatively prime to p.
Suppose that p is a prime number that divides the product ab of integers a and b.
Because p is “irreducible,” p must divide either a or b. More formally, if p does not
divide a, that is, a is not a multiple of p, then a is relatively prime to p, gcd(a, p) = 1,
and there exist integers i and j such that
1 = ia + jp
Multiplying this equation by b,
b = (ia)b + ( jp)b = i (ab) + ( jp)b
Because p 0 ab, ab can be written as kp, where k is an integer, so the previous
equation becomes
b = i(kp) + ( jp)b = (ik + jb)p
ik + jb an integer
so that p 0 b. This proves the following theorem.
tHeoReM oN DIvISIoN by PrIME NuMbErS
Let p be a prime number such that p 0 ab where a and b are integers. Then either
p 0 a or p 0 b.
PrACTiCe 11
a. Prove that if d is a positive integer such that d 0 a and d 0 b, then d 0 c, where c = ia + jb.
b. Prove that if d 0 c, then c ≥ d.
■
PrACTiCe 12 The integers 21 and 16 are relatively prime. Find i and j such that i (21) + j(16) = 1. ■
PrACTiCe 13 Extend the theorem on division by prime numbers as follows: Let p be a prime number such that p 0 a 1 a 2 … a k where each a i is an integer. Then p 0 a j for some j, 1 ≤ j ≤ k.
(Hint: You want to prove that this is true for every positive integer k—What proof technique
should you use?)
■
DeFinition rElaTIvEly PrIME
Two integers a and b are relatively prime if gcd(a, b) = 1.
From the theorem on gcd(a, b), it follows that a and b are relatively prime if
and only if there exist integers i and j such that
ia + jb = 1