Divisibility Proof by Euclidean Algorithm
Date: 02/20/2003 at 18:04:57 From: Julie Subject: Number Theory Let a and b be integers. Suppose that (a,b) = 1 (assuming the gcd exists). Prove that there exist integers x and y such that ax + ay = 1. Two examples I have worked are: 5x + 11y = (5,11) (5,11) = 1 so x and y can be several values like x = 1,2,3,...,9 and y = 1,2,3,4,6,7 and the other one is 175x + 24y = (175,24)= 1 x = 1 and y =1
Date: 02/20/2003 at 18:28:45 From: Doctor Roy Subject: Re: Number Theory Hi, Thanks for writing to Dr. Math. We can actually prove a much more general fact: If d = gcd(a,b), then d is the smallest positive integer that can be written as: ax + by = d for some x and y. Notice if gcd(a,b) = 1, this is the same statement as the one you wish to prove. Let's begin by assuming that g is the smallest positive number that can be written as ax + by for some x and y, or: ax + by = g Since d divides both a and b, d divides g as well, or: d <= g gcd(a,b) <= g We have that the gcd(a,b) <= g. Notice also that g must divide a and g must divide b. Here's the proof of that fact: If g does NOT divide a, then: a = u*g + r where u is some number and r is greater than or equal to 0 and less than g. Then: r = a - ug But g = ax + by: r = a - aux - buy = a*(1 - ux) + b*(-uy) But this violates the condition that g is the SMALLEST positive number that can be written as a linear combination of a and b unless r = 0. But if r = 0, g divides a. If g divides a, it must also divide the greatest common divisor, or: g <= GCD(a,b) So, we have: g <= gcd(a,b) and g >= gcd(a,b) The only way this is true is if g = gcd(a,b) = d. So, we have our proof. Does this help? Please feel free to write back with any questions you may have. - Doctor Roy, The Math Forum http://mathforum.org/dr.math/
Date: 02/20/2003 at 20:38:32 From: Julie Subject: Number Theory Thank you for help so far; however, I do not completely understand it yet. I have a couple more questions. I do not understand the difference between the numbers d and g. I also do not understand the proof that g does not divide a. How does this violate the condition that g is the smallest positive number? Also I know the Euclidean Algorithm is a = nq+r; how do you use this to solve for x and y in 5x +11y = 1? Thanks again. Julie
Date: 02/21/2003 at 12:21:30 From: Doctor Roy Subject: Re: Number Theory Hi, The idea is that d is what we KNOW is gcd(a,b). We want to show that g is equal to d. We do NOT know that this is true. We want to prove that d = g. But we cannot be sure of that. So, we have to show it. We want to show that g DOES divide a. It has to. We know the Euclidean algorithm: a = ng + r We want to show that r must be equal to 0 or else we get a contradiction. If r = 0, then g | a. r must be at least 0 and less than g. The remainder (that's what r is) is never greater than the divisor. For example, if we have 41/11 = 3 remainder 8 Notice the remainder is 8. It cannot be equal to 11. So, if we assume that g is the smallest possible number that can be written as: g = ax + by let's find the remainder when we divide a by g a = n*g + r r must be less than g and at least 0. If r is equal to g, we have made a mistake in writing the division algorithm. If a = n*g + r, we can substitute: a = n*g + r g = ax + by => Plug g into the first equation: a = n*(ax + by) + r a = nax + nby + r r = a - nax - nby r = a*(1 - nx) - b*ny Notice that r is a linear combination of a and b. So, r is a non- negative number that can be written in the form: r = a*Z + b*W where Z = (1 - nx) and W = -ny. But we already said that g was the SMALLEST positive number that could be written this way. This means that r is NOT positive or else g is not the SMALLEST positive number, because r must be less than g. That means that r must be zero. If r = 0, then: a = n*g + r a = n*g This means that g divides a. Using a similar proof, g divides b. If g divides both a and b, then g MUST divide gcd(a,b). Every divisor of both a and b divides the gcd. So, g <= gcd(a,b) And we have already shown that: g >= gcd(a,b) The only way both statements are true is if g = gcd(a,b). - Doctor Roy, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.