The Euclidean Algorithm And Diophantine Equations

The Euclidean Algorithm andDiophantine EquationsMath 149BurgerCalifornia State University, Fresno

Greatest Common Divisord is the greatest common divisor ofintegers a and b if d is the largest integerwhich is a common divisor of both a and b.Notation: d gcd(a, b)Example: 2, 7, and 14 are the onlyintegers that are common divisors of both42 and 56. Since 14 is the largest,gcd(42, 56) 14.

Use of the gcdReducing fractionsEx.42 14 3 3 56 14 4 4However: not all fractions are easily reduced!Ex. 80518633

The Division Algorithm(proof on p. 99)For integers a and b, with a 0, thereexist integers q and r such thatb qa r and 0 r a.

Euclidean Algorithm(p. 102)To find gcd(a, b) where b a:Divide b into a and let r1 be the remainder.Divide r1 into b and let r2 be the remainder.Divide r2 into r1 and let r3 be theremainder.Continue to divide the remainder into thedivisor until you get a remainder of zero.gcd(a, b) the last nonzero remainder.

Ex) Find gcd(8633, 8051)8051 97 83 83 8633 97 89 89

Theorem(3.2.2, p.105)For any nonzero integers a and b, thereexist integers x and y such thatgcd(a, b) ax by.Here’s how you use the EuclideanAlgorithm to write gcd(8633, 8051) as alinear combination of 8633 and 8051.

Use the Euclidean Algorithm to findgcd(8633, 8051).1 R.5828051 863313 R.485582 80511 R.97485 5825 R.097 485

Solve each division problem, except thelast one, for the remainder (r a – bq) .Take note of the quotient in each solution.1 R.5828051 8633 582 8633 1 805113 R.485582 8051 485 8051 13 5821 R.97485 582 97 582 1 4855 R.097 485

Use these equationsin reverse order to findthe linear combination.1: 582 8633 1 80512: 485 8051 13 5823: 97 582 1 48597 582 1 485Eq. 3 582 1 (8051 13 582) 14 582 1 8051Eq. 2Simp. 14 (8633 1 8051) 1 8051 14 8633 ( 15) 8051Eq. 1Simp.

Ex) Now use the Euclidean Algorithm to writegcd(486, 434) as a linear combination of 486and 434.

A Diophantine equation is any equation forwhich you are interested only in theinteger solutions to the equation.A linear Diophantine equation is a linearequation ax by c with integercoefficients for which you are interestedonly in finding integer solutions.Math 138/Burger

Theorem 1For any nonzero integers a and b, thereexist integers x* and y* such thatgcd(a,b) ax* by*.(Proof for Math 133!)When you have a linear Diophantine equation to solve,the first question you should ask about that Diophantineequation is whether or not the equation admits solutionsin integers.The following theorem tells you how to find the answer tothis question.

Theorem 3If gcd(a,b) c, then the linear Diophantineequation ax by c has no solution.Proof: Let d gcd(a,b). Then there areintegers r and s such that dr a and ds b.By way of contradiction, assume thatax by c does have a solution xo, yo.Then c axo byo drxo dsyo.But this says that d c since c d(rxo syo).Since this is a contradiction, theDiophantine equation has no solution.

Theorem 4If gcd(a,b) c, then the linear Diophantineequation ax by c has a solution.Proof: Let d gcd(a,b). Since d c, dp cfor some integer p.By Theorem 1, there are integers x* and y*such that d ax* by*.So c dp a(x*p) b(y*p).Hence ax by c has a solution, namelyxo x*p and yo y*p.

Q. If a linear Diophantineequation ax by c doesadmit a solution (since gcd(a,b) c),then how do you find it?

Using Division and Euclidean Algorithms toSolve Diophantine EquationsTo solve ax by c:1. Use the Division Algorithm to find d gcd(a,b).2. Use the Euclidean Algorithm to find x* and y*such that d ax* by*.3. Find p such that c dp. (p exists since d c.)4. Then xo x*p and yo y*p are solutions since c dp a(x*p) b(y*p).

Find a solution to the Diophantine equation172x 20y 1000. Use the Division Algorithm to findd gcd(172, 20).

Use the Euclidean Algorithm to find x* andy* such that d ax* by*.Solve for the remainder.8 R. 1220 172 12 172 1 20 Eq.11 R. 812 201 R. 48 12 8 20 1 12Eq.2 4 12 1 8Eq.3

Using theseequations we get:12 172 1 208 20 1 12Eq.1Eq.24 12 1 8Eq.34 12 1 8Eq.34 12 1 (20 1 12)Eq.24 2 12 1 20Simp.4 2 (172 8 20) 1 20Eq.14 2 172 ( 17) 20Simp.So x* 2 and y* -17

Solve 172x 20y 10004 2 172 ( 17) 20 Find p such that c dp.d gcd(172,20) 4c 1000so 1000 4·250.

Solve 172x 20y 10004 2 172 ( 17) 20 Then xo x*p and yo y*p are particularsolutions since c dp a(x*p) b(y*p).1000 4·250 [2 172 ( 17) 20 ]·2501000 172·(500) 20·(- 4250)So a ‘particular’ solution isxo 500 and y - 4250.

Theorem 4If the linear Diophantine equationax by c does have a solution, thenall such solutions are given byx xo (b/d)t and y yo – (a/d)twhere d gcd(a,b), xo, yo is aparticular solution to the equation andt ranges over the integers.

Solve 172x 20y 1000 Then all solutions are x xo (b/d)t andy yo – (a/d)t where t is an integer.From the equation 172x 20y 1000,we see that a 172 and b 20.From our previous work, xo 500,yo - 4250, and d 4.So the solutions, in integers, arex 500 5t and y - 4250 – 43twhere t ranges over the integers.

ExampleFind all positive solutions to theDiophantine equation 172x 20y 1000.we need to find those values of t for whichx 500 5t 0 and y - 4250 – 43t 0.

Find all positive integer solutions to the equation172x 20y 1000.All solutions are x 500 5t and y - 4250 – 43t.x 500 5t 0 t - 100.y - 4250 – 43t 0 t - 98.83 Since t must be an integer, t - 99.So - 100 t - 99.

Find all positive integer solutions to the equation172x 20y 1000.All solutions are x 500 5t and y - 4250 – 43t.We just found that - 100 t - 99.Since t must be an integer,- 100 t - 99 t - 99. So there isonly one positive solution to theDiophantine equation, namelyx 500 5t ··· 5 andy - 4250 – 43t ··· 7.

Euclidean Algorithm (p. 102) To find gcd(a, b) where b a: Divide b into a and let r 1 be the remainder. Divide r 1 into b and let r 2 be the remainder. Divide r 2 into r 1 and let r 3 be the remainder. Continue to divide the remainder into the divisor until you get a remainder of zero. gcd(a, b) the last nonzero remainder.