Try our Free Online Math Solver!

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 da, 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 writeup 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 ab and ac, then a(b + c).
1.2. Theorem. Let a, b, and c be integers. If ab and ac, then a(b − c).
1.3. Theorem. Let a, b, and c be integers. If ab and ac, then abc.
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 ab, then abc.
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 nonempty set
of natural numbers, then S has a smallest element.
We will just assume that the WellOrdering 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 