ABSTRACT ALGEBRA: OnLine Study Guide, §1.1

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 not equal bq for all q in Z, then we write b 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 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 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 = bq₁ + r₁, with 0 r₁ < b
b = r₁q₂ + r₂, with 0 r₂< r₁,
etc.

Since r₁ > r₂ > . . . , the remainders get smaller and smaller, and after a finite number of steps we obtain a remainder r_n+1 = 0. Thus gcd(a,b) = gcd(b,r₁) = . . . = r_n.

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:

m₁x + n₁y = gcd(a,b)
m₂x + n₂y = 0

Beginning with the matrix

we use the division algorithm to write a = bq₁ + r₁. We then subtract q₁ times the bottom row from the top row, to get

We next write b = r₁ q₂ + r₂, and subtract q₂ 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.

When working on questions involving divisibility you may find it useful to go back to Definition 1.1.1. If you expand the expression b | a by writing a = bq for some q in Z, then you have an equation to work with. This equation involves ordinary integers, and so you can use all of the things you already know (from high school algebra) about working with equations.
To show that b | a, try to write down an expression for a and expand, simplify, or substitute for terms in the expression until you can show how to factor out b.
Another approach to proving that b | a is to use the division algorithm (see Theorem 1.1.3 to write
a = bq + r, with 0 r < b.
Then to prove that b | a you only need to find some way to check that r = 0.
Theorem 1.1.6 states that 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. An integer is a linear combination of a and b if and only if it is a multiple of their greatest common divisor. This is really useful in working on questions involving greatest common divisors.

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 m² - n² is divisible by 8. Solution

28. Prove that if n is an integer with n > 1, then gcd (n-1, n²+n+1) = 1 or gcd (n-1, n²+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