# Division Algorithm, Euclidean Algorithm, Linear Diophantine Equations and Introduction to Modular Arithmetic

# Division Algorithm , Euclidean Algorithm, Linear Diophantine Equations and Introduction to Modular Arithmetic

Introduction and Goals. How can one natural number be
expressed as the product of

smaller natural numbers? This innocent sounding question leads to a vast field
of interconnections

among the natural numbers that mathematicians have been exploring for literally

thousands of years. The adventure begins by recalling the arithmetic from our
youth and

looking at it afresh. In this section we will explore the Division Algorithm ,
greatest common

divisors, the Euclidean Algorithm, and some consequences of these to finding
integer

solutions to linear equations. We will develop skills in proving theorems by
induction and

other means.

Many experiences in everyday life are cyclical—hours in the day, days in a week,
motions

of the planets. This concept of cyclicity gives rise to the idea of modular
arithmetic, which

develops the notion of numbers on a cycle. In this section, we will introduce
the basic idea

of modular arithmetic, which we will develop further in future sections.

Definitions.

1. The natural numbers are the numbers {1, 2, 3, 4, . .
.}.

2. The integers are {. . . − 3,−2,−1, 0, 1, 2, 3, . . .}.

3. Suppose a and d are integers, then d divides a, denoted d|a, if and only if
there is

an integer k such that a = kd.

4. Suppose that a, b, and n are integers, n > 0. We say that a and b are
congruent

modulo n if and only if n|(a − b). We denote this relationship as

a ≡ b (mod n)

and read these symbols as “a is congruent to b (mod n).”

We begin now with the first set of questions. “Theorem” denotes a mathematical

statement to be proved by you. For example,

Example Theorem. 3| − 9.

Then you would supply the proof, write it up clearly, and be prepared to present
your

proof at the board. Your write-up might look like this :

Example Theorem. 3| − 9.

Example Proof. By definition, 3| − 9 means that there exists an integer k such
that

−9 = 3k. So to prove that this definition is satisfied, we need to find an
integer k such that

−9 = 3k. Since −9 = 3 ยท (−3), the definition is satisfied, so 3| − 9 is true.

Example Theorem. 3 ≡ 7 (mod 2).

Example Proof. −4 = 2(−2). So, by definition, 2| − 4. So 2|(3 − 7). But 2|(3 −
7) is

the definition of 3 ≡ 7 (mod 2), so the theorem is proved.

Note: In giving proofs, rely on the definitions of terms and symbols , and feel
free to use

results that you have previously proved . Avoid using statements that you ‘know,’
but which

we have not yet proved.

1.1. Theorem. Let a, b, and c be integers. If a|b and a|c, then a|(b + c).

1.2. Theorem. Let a, b, and c be integers. If a|b and a|c, then a|(b − c).

1.3. Theorem. Let a, b, and c be integers. If a|b and a|c, then a|bc.

1.4. Question. Can you weaken the hypothesis of the previous theorem and still
prove

the theorem? Can you replace the conclusion by
and still prove the theorem?

1.5. Formulate your own theorem along the lines of the above theorems and prove
it.

1.6. Theorem. Let a, b, and c be integers. If a|b, then a|bc.

1.7. Examples. Prove your answers. Is 45 ≡ 9 (mod 4)? Is 37 ≡ 2 (mod
5)? Is 37 ≡ 3

(mod 5)? Is 31 ≡ −3 (mod 5)?

1.8. Exercise. For each of the following congruences, characterize all the
numbers m

that satisfy that congruence.

m ≡ 0 (mod 3),

m ≡ 1 (mod 3),

m ≡ 2 (mod 3),

m ≡ 3 (mod 3),

m ≡ 4 (mod 3).

1.9. Theorem. Let a and n be integers with n > 0. Then a ≡ a (mod n).

1.10. Theorem. Let a, b, and n be integers with n > 0. If a ≡ b (mod n), then b
≡ a

(mod n).

1.11. Theorem. Let a, b, c, and n be integers with n > 0. If a ≡ b (mod n) and b
≡ c

(mod n), then a ≡ c (mod n).

Note: If you are familiar with equivalence relations, you
may note that the previous three

theorems establish that congruence modulo n defines an equivalence relation on
the set of

integers. In the question before those theorems, 1.8, you described the
equivalence classes

modulo 3.

1.12. Theorem. Let a, b, c, d, and n be integers with n > 0. If a ≡ b (mod n)
and

c ≡ d (mod n), then a + c ≡ b + d (mod n).

1.13. Theorem. Let a, b, c, d, and n be integers with n > 0. If a ≡ b (mod n)
and

c ≡ d (mod n), then a − c ≡ b − d (mod n).

1.14. Theorem. Let a, b, c, d, and n be integers with n > 0. If a ≡ b (mod n)
and

c ≡ d (mod n), then ac ≡ bd (mod n).

1.15. Theorem. Let a, b, k, and n be integers with n > 0 and k > 0. If a ≡ b
(mod n),

then a^{k} ≡ b^{k} (mod n).

1.16. Question. Illustrate each of the above theorems with an example using
actual

numbers.

1.17. Theorem. Let a natural number n be expressed in base 10 as

Then if

1.18. Theorem. A natural number that is expressed in base 10 is divisible by 3
if and

only if the sum of its digits is divisible by 3.

1.19. Question. Devise and prove other divisibility criteria similar to the
preceding

one.

Well- Ordering Axion for the Natural Numbers. Let S be any non-empty set

of natural numbers, then S has a smallest element.

We will just assume that the Well-Ordering Axiom for the Natural Numbers is
true. So

feel free to use it whenever you wish.

The Division Algorithm. Let n and m be natural numbers. Then (existence part)

there exist integers q (for quotient) and r (for remainder) such that

m = nq + r and

0 ≤ r ≤ n − 1 (r is greater than or equal to 0
but less than or equal to n − 1). Moreover,

(uniqueness part) if q, q' and r, r' are any integers that satisfy m = nq + r =
nq' + r' with

0 ≤ r, r' ≤ n − 1, then q = q' and r = r'.

Prev | Next |