Excerpted from Beachy/Blair, Abstract Algebra, 2nd Ed. © 1996

§ 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 = p1m1 p2m2 · · · pnmn

where 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

(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 = p1a1 p2a2 · · · pnan     and     b = p1b1 p2b2 · · · pnbn ,

where ai 0 and bi 0 for all i (allowing use of the same prime factors.)
For each i let di = min { ai, bi } and let mi = max { ai, bi }. Then we have the following factorizations:
(a) gcd(a,b) = p1d1 p2d2 · · · pndn

(b) lcm[a,b] = p1m1 p2m2 · · · pnmn

§ 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(a2,b2) = 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 (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

```

```