Forward to §1.2 | Up | Table of Contents | About this document
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 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
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_{1} + r_{1}, with
0 r_{1} < b
b = r_{1}q_{2} + r_{2}, with
0 r_{2}< r_{1},
etc.
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
m_{1}x + n_{1}y = gcd(a,b)
m_{2}x + n_{2}y = 0
we use the division algorithm to write a = bq_{1} + r_{1}. We then subtract q_{1} times the bottom row from the top row, to get
We next write b = r_{1} q_{2} + r_{2}, and subtract q_{2} 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.
Here are several useful approaches you should be able to use.
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.
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^{2} - n^{2} is divisible by 8. Solution
28. Prove that if n is an integer with n > 1, then gcd (n-1, n^{2}+n+1) = 1 or gcd (n-1, n^{2}+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