Talk:Bézout's identity

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Number theory

I should do the searching... but just in case. Is it true that one can get the coefficients of less degree than the starting elements if one is in an Euclidean Domain? In the case of integers this amounts to saying that

there are x,y ∈ Z wiht |x|<max(a,b), |y|<max(a,b) with xa+yb=gcd(a,b)

Just in case. I'll try to find out though :) Pfortuny 09:26, 20 Apr 2004 (UTC)

Contents

[edit] proof

well, any proof is a proof (if it is one), but I like quite well the one on the french version of this page (considering the smallest element of { ax+by\in\N^* } which divides a and b.) — MFH:Talk 19:13, 6 October 2006 (UTC)

That being said, I am worried about this sentence from the first (English) proof:

Now, consider the numbers p, 2p, …, (q−1)p. None of these numbers is congruent to 0 modulo q, and they are also all distinct modulo q.

The statement is unassailable, but every proof of it I know uses either this identity, or prime factorisation, which, again, is almost invariably proven using this identity. Can it be justified independently? JadeNB 22:20, 8 March 2007 (UTC)

I was not happy with that proof myself. That was why I added the other proof here (most probably the exact same one as that used in French article). It uses only the most basic results about integers and is hence much less likely to fall foul of circularity.
Sanderling 10:24, 12 April 2007 (UTC)
As far as I can tell, this is the rearrangement property. And the proof of the rearrangement property relies on Euclid's lemma, which in turn relies on Bézout's identity, which in turn is relying on this rearrangement property. So yeah, it's circular. --Maian 00:18, 22 April 2007 (UTC)
OK, deleting it. JadeNB 01:56, 29 April 2007 (UTC)

[edit] Name

By the way, does anyone know why this is called an "identity"? Usually an identity consists of two expressions which are always equal; but, here, what we've got is a statement that a certain (simple) Diophantine equation has a solution. JadeNB 01:59, 29 April 2007 (UTC)

I believe the identity is that the set of linear combinations of x & y is identical to the set of multiples of gcd(x,y). Blokhead 01:32, 14 May 2007 (UTC)

[edit] confused or is that even a proof??

Given any equation of the form ax+by=d , the line can be drawn. a,b,d>0

The question is to prove that integer "x and y" exist.

the proof however seems to assume integer x and y exist and then say "because d is the smallest positive integer which satisfies this , d is GCD(a,b) or there exists a value smaller than d that satisfies this, called r , so d is not the smaallest...(somewhat as I could make out)".

It doesnt even assume "a is given and b is given and x and y may not exist" it assumes "a and b exist, x and y exist and set of values which contain d as the minimal exists, and because d is minimal r<d cannot exist".

take 9x+3y=5; we obviously need to show that x and y do not exist else r=4 exists, etc. or can that be taken for granted?

How do I prove that integer x and y exist? Is making the assumption "that it exists" valid? Does the theorem state "if integer x,y exist then d is gcd(a,b)" or does it state "if d is gcd(a,b) integer x and y must exist"?


Take the trivial case d=1 ax+by=1 a,b >0

can one prove integer x and y exist.

Perhaps my understanding of the statement is wrong? —The preceding unsigned comment was added by 220.227.207.194 (talk • contribs).

In the proof, the set S of all numbers expressible in th form ax+by is studied. And it is shown that the smallest number from S is a common divisor of a and b. I.e., d in the proof does not stand for the GCD(a,b). It stands for the smallest element of S. And later, we are able to show, that this d is the GCD. --Kompik 14:47, 17 July 2007 (UTC)


given 5x+20y=1 we do not know if d is gcd(a,b) we assume d is the smallest element in S and d=1 (this is true for any equation and the 1st number that will come to mind is d=1) now I follow every step in the proof to show that there exists no 0<r<d in other words for d=1 a=ad+0 , b=bd+0 ; hence 0<r<d does not exist however d=1 does not yield a solution to the above equation—Preceding unsigned comment added by 220.227.207.194 (talk • contribs) 13:59, 30 August 2007

No. We are not looking at any equations at all! We are looking at a's and b's. So given a = 5 and b = 20, then S is the set of all numbers 5x + 20y, the smallest element of which is 5. And 5 is the gcd(5,20). I have no idea where your 1 came from. So obviously there exists x's and y's such that 5x + 20y = gcd(5,20), which is what the identity says. --Spoon! 16:28, 9 September 2007 (UTC)

yeah but how do i show that the smallest element of S is <something> say given 6x+9y=d , d is not known. now how do i start? d can be 1,2,3,4,5...infinity.. right? now assume d=1 how do i prove no solution exists. all i saying is that the proof seems to assume that a smallest d exists, and then shows that if d is not the smallest, then we have a contradiction. Now if one assumes d=1 how does one show the contradiction.. —Preceding unsigned comment added by 220.227.207.194 (talk • contribs) 09:17, 10 September 2007

d is defined to be the smallest of S. What d is doesn't matter. All we want to do is show that it is equal to gcd(a, b).
Think about all the positive numbers that can be obtained by 6 × (some integer) + 9 × (some other integer). Can you make 1 out of that? No. Can you make 2? No. So S doesn't necessarily contain all numbers. For the purposes of the proof, we don't actually care what S is; so long as it is not empty. Whatever it is, we define d to be its smallest element.
Think about what we are trying to prove. We are trying to prove that, for example, there exists integers x and y such that 6x + 9y = gcd(6, 9) = 3, i.e. that 3 is in S. And how we are proving that is to show that 3 is actually the smallest element in S (i.e. d). The proof is kind of backwards.

--Spoon! 04:22, 11 September 2007 (UTC)

thanks for your time and patience..a couple of questions: Can you make 1 out of that? No. =>Exactly, how do you prove that? The point is that the proof is not foolproof. can i make 1 out of that, yes i can...umm no i cant...? is a very grey area, is it not? example 2867x+6893y=d, is anything obvious at first glance? no right? so now i try to use the proof to show a contradiction, i assume the smallest element in S is 1 and I get 2867x+6893y=1, now what?

The crux of the proof is that the set of S of numbers of the form 2867x+6893y (where x and y are any integers) must contain a smallest positive member - we call this number d. We don't have to guess the value of d - we just use the fact that it exists. Now suppose that 6893 is not a multiple of d. Then 6893 = kd + r where 0<r<d. So we would have
6893 = kd + r = k(2867x + 6893y) + r = 2867(kx) + 6893(ky) + r
\Rightarrow r=-2867(kx)-6893(ky-1)
But this shows that r is in S. And remember that 0<r<d, so this contradicts the fact that d is the smallest positive member of S. The only way to avoid this contradiction is if 6893 is a multiple of d. Similarly 2867 must also be a multiple of d. So d is a common divisor of 6893 and 2867.
And if c is any other common divisor of both 6893 and 2867 then c must certainly be a divisor of 2867x+6893y ... but this means c is a divisor of d. So d is not just some common divisor of 6893 and 2867 - it is their greatest common divisor. Gandalf61 15:49, 11 September 2007 (UTC)

=> why the: And if c is any other common divisor of both 6893 and 2867 then c must certainly be a divisor of 2867x+6893y ... but this means c is a divisor of d.

nothing in the proof says that if "d" is "any divisor" of 6893x+2867y then 6893x+2867y=d does not exit, does it? or that value of "d" is/is not the smallest in S?

In other words the smallest value in S can be anything. we find a value which we could presume is the smallest, which satisifies the r=0 condition, but we still have to show that the value of "d" thus obtained is not the smallest in "S". I could be ..right?

Hence my original statement: if I find a d, can I prove x and y do not exist for that "d"? Is making the assumption that it does not exist valid?

Say I find any "d" so that r=0, why am I wrong in saying that 6893x+2867y=d exists and that value of "d" is the smallest in S..? So I find d=1, now how do i prove that 6893x+2867y=1 does not exist? and if a c exists, such that it divides both 6893 and 2867, then c > d is also true, correct? In other words any divisor of 6893 and 2867 will satisfy the remainder theorem condition and also have no 0<r<d as a value, but you still have to prove that the value of d that has hence been obtained is not the smallest? I have given the example of using d=1 above, I know a c>1 may exist (note c>d) but I still have to show that this value "d" is not the smallest in S, is that not true? seems to me the proof is circular, it assumes it is correct before it starts to prove anything, and then again uses itself to prove the same.

—Preceding unsigned comment added by 220.227.207.194 (talk) 06:30, 12 September 2007 (UTC)
Okay. Let's start again from square one. Let's use 120 and 36 as an example (forget 6893 and 2867).
  1. S is the set of all numbers of the form 120x+36y, where x and y are integers. So S contains 120+36=156, 120-36=84, 120-72=48, 240-144=96 etc. etc. Write down some more members of S. You might notice that all the members of S that you write down are even. Can you see some other properties that all the members of S might have ?
  2. If c is a number that divides both 120 and 36 (a "common divisor"), then it will divide any number of the form 120x+36y - in other words, it will divide every member of S. So 1, 2, 3, 4 , 6 and 12 (the common divisors of 36 and 120) divide every member of S.
  3. Notice that we are not saying that every common divisor c is itself is a member of S - usually it isn't. 1 cannot be in S because we know that all the members of S are even. 2 cannot be in S because we know that all the members of S are multiples of 3 etc.
  4. In fact, the only common divisor of 36 and 120 that can possibly be in S is the largest of the common divisors, which is 12. This is because if some smaller common divisor is in S then it is not a multiple of 12 (because it is smaller than 12) - but we know that every number in S must be a multiple of 12. So 12 could be in S - but we aren't sure that it is in S yet.
  5. Now we think about the smallest positive member of S, which we call d. The proof outlined in the article shows that d must be a common divisor of 36 and 120 because if it wasn't, then we could find a smaller positive member of S.
  6. But we know that the only common divisor of 36 and 120 than can possibly be in S is the greatest common divisor, 12. So d (the smallest positive member of S) must be 12 (the greatest common divisor of 36 and 120).
  7. So far, we haven't actually found values of x and y that will make 120x+36y equal to 12 - we have just shown that they must exist. The extended Euclidean algorithm is a way of finding values of x and y that will work - in this case x=1 and y=-3 works, because 120-108=12.
Now, read this through carefully, and try to understand how each step follows from the ones before. Don't make any assumptions about what think the proof is saying - just follow the steps as I have written them. If there is a step that you can't follow, then ask a question on my talk page. Gandalf61 12:17, 12 September 2007 (UTC)

comments posted on Gandalf's page the only question is why would any common divisor of a and b not be a suitable candidate for "d" , and what if such a "c" does not exist, is the division algorithm sufficient on its own to prove the same? —Preceding unsigned comment added by 220.227.207.194

Seems the proof assumes d<=a and d<=b, see posts on gandalf's page my talk page and Talk:Division_algorithm#misquoted_elsewhere.3F. In which case we do not even need the division algorithm —Preceding unsigned comment added by 220.227.207.194 (talk) 07:54, 17 September 2007 (UTC)

[edit] nice proof

Well this one seemed more rigorous to me: http://www.cut-the-knot.org/blue/Euclid.shtml Essentially works backwards from Euclids algo to get here. Does anyone know a way to prove this using co-ordinate geometry? Note that this is the equation of a line given:ax+by=gcd(a,b), show that integers x,y exist on this line.

However note that this too shows that a solution of the form ax+by=gcd(a,b) exists It does not however show that gcd(a,b) is the smallest possible solution. —Preceding unsigned comment added by 220.227.207.194 (talk) 07:01, 2 April 2008 (UTC)

I would really appreciate any links to such a site. —Preceding unsigned comment added by 220.227.207.194 (talk) 06:46, 2 April 2008 (UTC)