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

1.20. Illustrate the division algorithm for m = 22, n = 11; m = 33, n = 45; m = 277,
n = 4.

1.21. Prove the existence part of the Division Algorithm. (Hint: Given n and m,
how will you define q? Once you choose this q, then how is r chosen? Then show that
0 ≤ r ≤ n − 1.)

1.22. Prove the uniqueness part of the Division Algorithm. (Hint: If nq + r = nq' + r',
then nq − nq' = r' − r. Use what you know about r and r' as part of your argument that
q = q'.)

1.23. Theorem. Let a, b, and n be integers with n > 0. Then a ≡ b (mod n) if and
only if a and b have the same remainder when divided by n. Equivalently , a ≡ b (mod n) if
and only if when and , then

Definitions.

1. The greatest common divisor of two integers a and b is the largest
integer d such that d|a and d|b. The greatest common divisor of two integers a and b is
denoted gcd(a, b) or (a, b).

2. If gcd(a, b) = 1, then a and b are said to be relatively prime.

1.24. Question. Find (36, 22), (45,−15), (296,−88), (0, 256), and (15, 28).

1.25. Theorem. Let a, n, b, r, and k be integers. If a = nb + r and k|a and k|b, then
k|r.

1.26. Theorem. Let  and be integers. If , then (a, b) =
Similarly, if , then

1.27. Question. As an illust ration of the above theorem, note that

51 = 3 · 15 + 6
15 = 2 · 6 + 3
6 = 2 · 3 + 0.

Show that if a = 51 and b = 15, then (51, 15) = (6, 3) = 3.

1.28. Question (Euclidean Algorithm). Using the previous theorem and the Division
Algorithm successively, devise a procedure for finding the greatest common divisor of two
integers.

1.29. Use the Euclidean Algorithm to find (96, 112), (288, 166), and (175, 24).

1.30. Find integers x and y such that 175x + 24y = 1.

1.31. Theorem. Let a and b be integers. The greatest common divisor of a and b equals
1 (i.e., (a, b) = 1) if and only if there exist integers x and y such that ax + by = 1.

(Note: This theorem is an ‘if and only if’ theorem, so you must prove two theorems: (1) If
(a, b) = 1, then there exist integers x and y such that ax + by = 1. And (2) If there exist
integers x and y with ax + by = 1, then (a, b) = 1. The hint for the first part is to use the
Euclidean Algorithm. Do some examples by taking some pairs of relatively prime integers,
doing the Euclidean Algorithm, and seeing how to find the x and y. It is a good idea to start
with an example where the Euclidean Algorithm takes just one step , then do an example
where the Euclidean Algorithm takes two steps, then three steps, then look for a general
procedure.)

1.32. Theorem. For any integers a and b, there are integers x and y such that ax+by =
(a, b).

1.33. Theorem. Let a, b, and c be integers. If a|bc and (a, b) = 1, then a|c.

Theorems 1.30 and 1.31 begin to address the question : Given integers a, b, and c, when
do there exist integers x and y that satisfy the equation ax+by = c? When we seek integer
solutions to an equation , the equation is called a Diophantine equation.

1.34. Question. Suppose there is a solution to the linear Diophantine equation ax +
by = c. What condition does c satisfy in terms of a and b ?

1.35. Question. Make a conjecture by completing the fol lowing theorem statement.
Conjecture. Given integers a, b, and c, there exist integers x and y that satisfy the equation
ax + by = c if and only if . Prove your conjecture.

1.36. Theorem. Given integers a, b, and c, there exist integers x and y that satisfy the
equation ax + by = c if and only if (a, b)|c.

1.37. Question. For integers a, b, and c, consider the linear Diophantine equation
ax + by = c. Suppose integers and satisfy the equation, that is, . What
other values , and , also satisfy ax+by = c? Formulate a conjecture that
answers this question. Devise some numerical examples to ground your exploration. For
example, 6(−2) + 15 · 2 = 18. Can you find other integers x and y such that 6x + 15y = 4?
How many other pairs of integers x and y can you find? Can you find infinitely many other
solutions?

1.38. Question (Euler). A farmer lays out the sum of 1,770 crowns in purchasing
horses and oxen. He pays 31 crowns for each horse and 21 crowns for each ox. What are
the possible numbers of horses and oxen that the farmer bought?

1.39. Theorem. Let a, b, c, , and be integers such that . Then
the integers and also satisfy the linear Diophantine equation
ax + by = c.

1.40. Question. If a, b, and c are integers and the linear Diophantine equation ax+ by =
c has at least one integer solution, find a general expression for all the integer solutions to

1.41. Theorem. Let a, b, c, be integers. Then the equation ax + by = c has a solution
if and only if (a, b)|c. If  is a solution, that is, , then for every integer k,
the integers and also satisfy the linear Diophantine equation
ax + by = c. Moreover, every solution to the linear Diophantine equation ax + by = c is of
this form.

1.42. Theorem. If a and b are integers and k is a natural number, then gcd(ka, kb) =
k gcd(a, b).

1.43. Formulate a definition. For natural numbers a and b, give a suitable definition
for the least common multiple of a and b , denoted lcm(a, b). Construct and compute some
examples.

1.44. Theorem. If a and b are natural numbers, then gcd(a, b) lcm(a, b) = ab.

1.45. Corollary. If a and b are natural numbers, then lcm(a, b) = ab if and only if
gcd(a, b) = 1.

1.46. Big Picture Question: How are the ideas of greatest common divisor and solutions
to linear Diophantine equations related?

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of April 27th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!