ABSTRACT ALGEBRA: OnLine Study Guide, §1.2

Forward to §1.3 | Back to §1.1 | Up | Table of Contents | About this document

§ 1.2 Primes

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.

(a) If b | ac, then b | (a,b)c.

(b) If b | ac and (a,b) = 1, then b | c.

(c) If b | a, c | a and (b,c) = 1, then bc | a.

(d) (a,bc) = 1 if and only if (a,b) = 1 and (a,c) = 1 .

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 = p₁^m₁ p₂^m₂ · · · p_n^m_n

where p₁ < p₂ < · · · < p_n and the exponents m₁, m₂ , . . . , m_n 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

(i) m is a multiple of both a and b, and

(ii) any multiple of both a and b is also a multiple of m.

We will use the notation lcm[a,b] for the least common multiple of a and b.

Proposition 1.2.9. Let a and b be positive integers with prime factorizations

a = p₁^a₁ p₂^a₂ · · · p_n^a_n and b = p₁^b₁ p₂^b₂ · · · p_n^b_n ,

where a_i

0 and b_i

0 for all i (allowing use of the same prime factors.)
For each i let d_i = min { a_i, b_i } and let m_i = max { a_i, b_i }. Then we have the following factorizations:

(a) gcd(a,b) = p₁^d₁ p₂^d₂ · · · p_n^d_n

(b) lcm[a,b] = p₁^m₁ p₂^m₂ · · · p_n^m_n

§ 1.2 Primes: Solved problems

Proposition 1.2.2 states that integers a and b are relatively prime if and only if there exist integers m and n with ma + nb = 1. This is one of the most useful tools in working with relatively prime integers. Remember that this only works in showing that gcd (a,b) = 1. More generally, if you have a linear combination ma + nb = d, it only shows that gcd (a,b) is a divisor of d (refer back to Theorem 1.1.6).

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(a²,b²) = 1. Solution

28. 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

29. Let m and n be positive integers. Prove that
gcd (2^m - 1, 2ⁿ - 1) = 1 if and only if gcd (m,n) = 1. Solution

30. Prove that gcd (2n² + 4n - 3, 2n² + 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