152
Proofs, Induction, and Number Theory
tecHniQueS
• Write the gcd(a, b) as a linear combination of a and b.
• Test whether a given positive integer is prime or, if
not, find its prime factorization.
• Compute the Euler phi function φ(n) for a positive
integer n.
MAin iDeAS
• Every integer ≥ 2 is prime or can be uniquely factored into prime numbers (fundamental theorem of
arithmetic).
• Two integers a and b are relatively prime if a linear
combination of a and b can be found that equals 1.
• If n is not prime, it has a prime factor no greater
than !n.
• An infinite number of prime numbers exist.
• There is no efficient algorithm to decide whether a
positive integer n is prime, or to find the prime factors of n if n is not itself prime.
• Given n written as a product of primes, there is a
formula to compute φ(n), the number of positive
integers ≤ n and relatively prime to n.
eXeRciSeS 2.4
Exercises 1–6 refer to Exercises 7–12 in Section 2.3
1. Write gcd(308, 165) as a linear combination of 308 and 165.
2. Write gcd(2420, 70) as a linear combination of 2420 and 70.
3. Write gcd(735, 90) as a linear combination of 735 and 90.
4. Write gcd(8370, 465) as a linear combination of 8370 and 465.
5. Write gcd(1326, 252) as a linear combination of 1326 and 252.
6. Write gcd(1018215, 2695) as a linear combination of 1018215 and 2695.
For Exercises 7–12, test whether n is prime and, if not, find its decomposition as a product of primes.
7. n = 1729
8. n = 1789
9. n = 1171
10. n = 1177
11. n = 8712
12. n = 29575
Exercises 13–18 refer to Exercises 7–12 in Section 2.3
13. Find gcd(308, 165) by unique factorization into products of primes.
14. Find gcd(2420, 70) by unique factorization into products of primes.
15. Find gcd(735, 90) by unique factorization into products of primes.
16. Find gcd(8370, 465) by unique factorization into products of primes.
17. Find gcd(1326, 252) by unique factorization into products of primes.
18. Find gcd(1018215, 2695) by unique factorization into products of primes.
19. The least common multiple of two positive integers a and b, lcm(a, b) is the smallest integer n such that
a 0 n and b 0 n. Like the gcd(a, b), the lcm(a, b) can be found from the prime factorizations of a and b.
Describe (in words) the gcd and the lcm in terms of the prime factors of a and b.
20. Prove that for any positive integers a and b, a # b = gcd(a, b) # lcm(a, b). (Hint: consider both a and b in
their factored form as a product of primes.)
S e c t i o n 2 . 4 review
W
Proofs, Induction, and Number Theory
tecHniQueS
• Write the gcd(a, b) as a linear combination of a and b.
• Test whether a given positive integer is prime or, if
not, find its prime factorization.
• Compute the Euler phi function φ(n) for a positive
integer n.
MAin iDeAS
• Every integer ≥ 2 is prime or can be uniquely factored into prime numbers (fundamental theorem of
arithmetic).
• Two integers a and b are relatively prime if a linear
combination of a and b can be found that equals 1.
• If n is not prime, it has a prime factor no greater
than !n.
• An infinite number of prime numbers exist.
• There is no efficient algorithm to decide whether a
positive integer n is prime, or to find the prime factors of n if n is not itself prime.
• Given n written as a product of primes, there is a
formula to compute φ(n), the number of positive
integers ≤ n and relatively prime to n.
eXeRciSeS 2.4
Exercises 1–6 refer to Exercises 7–12 in Section 2.3
1. Write gcd(308, 165) as a linear combination of 308 and 165.
2. Write gcd(2420, 70) as a linear combination of 2420 and 70.
3. Write gcd(735, 90) as a linear combination of 735 and 90.
4. Write gcd(8370, 465) as a linear combination of 8370 and 465.
5. Write gcd(1326, 252) as a linear combination of 1326 and 252.
6. Write gcd(1018215, 2695) as a linear combination of 1018215 and 2695.
For Exercises 7–12, test whether n is prime and, if not, find its decomposition as a product of primes.
7. n = 1729
8. n = 1789
9. n = 1171
10. n = 1177
11. n = 8712
12. n = 29575
Exercises 13–18 refer to Exercises 7–12 in Section 2.3
13. Find gcd(308, 165) by unique factorization into products of primes.
14. Find gcd(2420, 70) by unique factorization into products of primes.
15. Find gcd(735, 90) by unique factorization into products of primes.
16. Find gcd(8370, 465) by unique factorization into products of primes.
17. Find gcd(1326, 252) by unique factorization into products of primes.
18. Find gcd(1018215, 2695) by unique factorization into products of primes.
19. The least common multiple of two positive integers a and b, lcm(a, b) is the smallest integer n such that
a 0 n and b 0 n. Like the gcd(a, b), the lcm(a, b) can be found from the prime factorizations of a and b.
Describe (in words) the gcd and the lcm in terms of the prime factors of a and b.
20. Prove that for any positive integers a and b, a # b = gcd(a, b) # lcm(a, b). (Hint: consider both a and b in
their factored form as a product of primes.)
S e c t i o n 2 . 4 review
W