Forward to §1.3 | Back to §1.1 | Up | Table of Contents | About this document
Definition 1.2.1. The nonzero integers a and b are said to be relatively prime if (a,b) = 1.
Proposition 1.2.2. Let a,b be nonzero integers. Then (a,b) = 1 if and only if there exist integers m,n such that
ma + nb = 1 .
Proposition 1.2.3. Let a,b,c be integers.
Definition 1.2.4. An integer p > 1 is called a prime number if its only divisors are ± 1 and ± p. An integer a > 1 is called composite if it is not prime.
Lemma 1.2.5. [Euclid] An integer p > 1 is prime if and only if it satisfies the following property: If p | ab for integers a and b, then either p | a or p | b.
Theorem 1.2.6. [Fundamental Theorem of Arithmetic] Any integer a > 1 can be factored uniquely as a product of prime numbers, in the form
a = p1m1 p2m2 · · · pnmnwhere p1 < p2 < · · · < pn and the exponents m1, m2 , . . . , mn are all positive.
Theorem 1.2.7. [Euclid] There exist infinitely many prime numbers.
Definition 1.2.8. A positive integer m is called the least common multiple of the nonzero integers a and b if
Proposition 1.2.9. Let a and b be positive integers with prime factorizations
a = p1a1 p2a2 · · · pnan and b = p1b1 p2b2 · · · pnbn ,where ai 0 and bi 0 for all i (allowing use of the same prime factors.)
Since the fundamental theorem of arithmetic (Theorem 1.2.6) is proved in this section, you now have some more familiar techniques to use, involving factorization into primes.
23. (a) Use the Euclidean algorithm to find gcd (1776,1492).
(b) Use the prime factorizations of 1492 and 1776 to find gcd (1776,1492). Solution
24. (a) Use the Euclidean algorithm to find gcd (1274,1089).
(b) Use the prime factorizations of 1274 and 1089 to find gcd (1274,1089). Solution
25. Give the lattice diagram of all divisors of 250. Do the same for 484. Solution
26. Find all integer solutions of the equation xy + 2y - 3x = 25. Solution
27. For positive integers a,b, prove that gcd (a,b) = 1 if and only if gcd(a2,b2) = 1. Solution
Prove that n - 1 and 2n - 1 are relatively prime,
for all integers n > 1.
Is the same true for 2n - 1 and 3n - 1? Solution
Let m and n be positive integers.
gcd (2m - 1, 2n - 1) = 1 if and only if gcd (m,n) = 1. Solution
30. Prove that gcd (2n2 + 4n - 3, 2n2 + 6n - 4) = 1, for all integers n > 1. Solution
Solutions to the problems | Forward to §1.3 | Back to §1.1 | Up | Table of Contents