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

Forward to §1.2 | Up | Table of Contents | About this document

§ 1.1 Divisors

The set {..., -2, -1, 0, 1, 2, 3, ...} is called the set of integers, and will be denoted by Z.

Definition 1.1.1. An integer a is called a multiple of an integer b if a = bq for some integer q. In this case we also say that b is a divisor of a, and we use the notation b | a.

In the above case we can also say that b is a factor of a, or that a is divisible by b. If b is not a divisor of a, meaning that a is not equal to bq for all q in Z, then we write b is not a divisor of a. The set of all multiples of an integer a will be denoted by

aZ = { m in Z | m = aq   for some   q in Z }.

Axiom 1.1.2. [Well-Ordering Principle] Every nonempty set of natural numbers contains a smallest element.

Theorem 1.1.3. [Division Algorithm] For any integers a and b, with b > 0, there exist unique integers q (the quotient) and r (the remainder) such that a = bq + r, with 0 is less than or equal to r < b.

Theorem 1.1.4. Let I be a nonempty set of integers that is closed under addition and subtraction. Then I either consists of zero alone or else contains a smallest positive element, in which case I consists of all multiples of its smallest positive element.

Definition 1.1.5. A positive integer d is called the greatest common divisor of the nonzero integers a and b if

(i) d is a divisor of both a and b,   and

(ii) any divisor of both a and b is also a divisor of d.
We will use the notation gcd(a,b), or simply (a,b), for the greatest common divisor of a and b.

Theorem 1.1.6. Any two nonzero integers a and b have a greatest common divisor, which can be expressed as the smallest positive linear combination of a and b.
    Moreover, an integer is a linear combination of a and b if and only if it is a multiple of their greatest common divisor.

Euclidean Algorithm. The greatest common divisor of two numbers can be computed by using a procedure known as the Euclidean algorithm.

First, note that if a is not equal to 0 and b | a, then gcd(a,b) = |b|. The next observation provides the basis for the Euclidean algorithm. If a = bq + r, then (a,b) = (b,r). Thus given integers a > b > 0, the Euclidean algorithm uses the division algorithm repeatedly to obtain

a = bq1 + r1,   with 0 less than or equal to r1 < b
b = r1q2 + r2,   with 0 less than or equal to r2< r1,

Since r1 > r2 > . . . , the remainders get smaller and smaller, and after a finite number of steps we obtain a remainder rn+1 = 0. Thus gcd(a,b) = gcd(b,r1) = . . . = rn.

Euclidean Algorithm (matrix form). The Euclidean algorithm can be put into a convenient matrix format that keeps track of the remainders and linear combinations at the same time. To find gcd(a,b), assuming that a > b > 0, the idea is to start with the following system of equations:

x       = a
      y = b

and, by using elementary row operations, to find an equivalent system of the following form:

m1x + n1y = gcd(a,b)
m2x + n2y = 0          

Beginning with the matrix

we use the division algorithm to write a = bq1 + r1. We then subtract q1 times the bottom row from the top row, to get

We next write b = r1 q2 + r2, and subtract q2 times the top row from the bottom row. This gives the matrix

and it can be checked that this algorithm produces rows in the matrix that give each successive remainder, together with the coefficients of the appropriate linear combination of a and b. The procedure is continued until one of the entries in the right-hand column is zero. Then the other entry in this column is the greatest common divisor, and its row contains the coefficients of the desired linear combination.

§ 1.1 Solved Problems

Before working through the solved problems for this section, you need to make sure that you are familiar with all of the definitions and theorems in the section. In many cases, the proofs of the theorems contain important techniques that you need to copy in solving the exercises in the text.

Here are several useful approaches you should be able to use.

22. Find gcd (435, 377), and express it as a linear combination of 435 and 377.     Solution

23. Find gcd (3553, 527), and express it as a linear combination of 3553 and 527.     Solution

24. Which of the integers 0, 1, . . . , 10 can be expressed in the form 12m + 20n, where m,n are integers?     Solution

25. If n is a positive integer, find the possible values of gcd (n, n+10).     Solution

26. Prove that if a and b are nonzero integers for which a | b and b | a, then b = ± a.     Solution

27. Prove that if m and n are odd integers, then m2 - n2 is divisible by 8.     Solution

28. Prove that if n is an integer with n > 1, then gcd (n-1, n2+n+1) = 1 or gcd (n-1, n2+n+1) = 3.     Solution

29. Prove that if n is a positive integer, then

if and only if 4 | n.     Solution

30. Give a proof by induction to show that each number in the sequence 12, 102, 1002, 10002, . . . , is divisible by 6.     Solution

Solutions to the problems | Forward to §1.2 | Up | Table of Contents