Talk:Bézout's identity

New Proof

I fixed the proof for two co-primes. I am new to this and may have made many non-standard math formatting, etc. If you can review, please do. Thanks (SLB December 2016) — Preceding unsigned comment added by Sandybultena (talk • contribs) 02:28, 14 December 2016 (UTC)

Untitled

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)

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)

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)

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)

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)

A simple Proof of Bezout Identity by Nilaish

According to my paper no. 2 , VOL. No. 2, published on my journal ( http://nilaish.livejournal.com/ ), It is now stated that my proof is much simpler. I'll try to explain it here, we have, Linear Diophantine Equation , $ax+by=c$ , is general Linear Diophantine Equation, as per my solution its general solutions are, $x=(c^{2}+1)/2ac;y=(c^{2}-1)/2bc$ , as we notice when $c=1$ , then LDE has infinite integral solutions, c other than 1, it has non integral solutions. So, my this citation is much simpler than the provided proof. To know more about my paper no. 2, please visit my journal. I think that this can be treated as considerable substance to treat various LDEs, which can be verified using my formulae. —Preceding unsigned comment added by Nilaish (talk • contribs) 15:32, June 20, 2008

Hmmm ... something clearly wrong there, because when c = 1 you have y = 0 and x = 1/a, which is only an integral solution in the special case when a is 1. Gandalf61 (talk) 10:32, 21 June 2008 (UTC)

From the above comment I want be more clear about my disscussion, that a,b,c belongs to integers,x and y are variables. But , the user is not saying about b as said about a. As the scheme of values permissible for my formulae is, 1. In the above comment the value of y is written wrong, as when $c=1,thenthisformulaecan'tbeused.$ , as we need to solve it directly using my theorem, in my paper above mentioned, from it is more clear. 2. In special case cited above is very remarkable for the nature of solution of LDE. The solution for $y=1/b.$ , please refer my paper on it. nilaish (talk) 12:58, 21 June 2008 (UTC)

Musical Intervals example

I think I understand the identity and the solutions but I don't understand this section:

 ... then the K'th ratio in this set will be:
 (k19 + 5)/(k15 + 4)   k=0, 1, 2 ...

Can someone please fill in some detail on this and how the "approximation" part comes in? What "set" does this refer to? The multivalued solution set for x, y?

Jensigner (talk) 02:15, 23 August 2010 (UTC)

I think I don't understand the musical intervals section at all, nor apparently does the person who wrote it. Can anyone who understands what this is supposed to be about rewrite it in understandable language? Maybe it would be an idea to start explaining what the problem is with musical intervals in the first place. If this cannot be done, I think the section should be removed. Marc van Leeuwen (talk) 21:18, 3 March 2011 (UTC)

I can't understand the point of that section either. It adds nothing useful to the article, so I have removed it. Gandalf61 (talk) 10:07, 4 March 2011 (UTC)

Why was my section on musical intervals deleted?

To anybody with a background in musical theory, it is "goes without saying" that the GCD between two or more sine waves corresponds to the frequency of that wave. Furthermore, if we stay within the realm of small whole numbers (the tuning system called Just Intonation or JI), then this GCD acts as the Tonic or key centre in musical harmony. The Bezout's ID technique I described has been used as a standard method for finding approximate musical intervals for centuries. The fact that a few 'pure' mathematicians believe they can decide for the rest of the world what is of universal relevance is arrogant to say the least. Since 1928 it has been known that the universe is wave-like and is not based on infinitesimal points of zero dimensions. Indeed, questions like "What "set" does this refer to?", as if wave theory could ever be reduced to a problem of non-existent number sets, could be taken as a measure of the extent to which 'pure' maths has allowed itself to be removed from reality. But at the end of the day, it was really none of your business to decide amongst yourselves to delete my article, based as it was on your own lack of understanding. I'll get back to it when I'm ready. —Preceding unsigned comment added by 122.108.152.136 (talk) 08:32, 28 March 2011 (UTC)

You say "it was really none of your business to decide amongst yourselves to delete my article" - but, actually, it is entirely the business of other editors to decide whether to keep, amend or remove another editor's contributions, because Wikipedia is a collaborative venture. There is no such thing as "my article" - see WP:OWN. The musical intervals example was removed because no-one could understand it - see discussion above. If you are going to reinstate it, you should try to explain it more clearly, and provide a reliable source to show that it is not your own original research. Gandalf61 (talk) 15:31, 28 March 2011 (UTC)

As someone who is both a 'pure' mathematician and has some background in musical theory, let me try to say something about the musical contents of the remark. When you say "GCD between two or more sine waves" this is at first sight unclear: GCD operates on integers (or on polynomials, but I don't think that is relevant her), sine waves are functions of a real variable. What you probably mean is taking the GCD of their frequencies (which makes the remainder of the sentence "corresponds to the frequency of that wave" unclear, but it is so anyway since there were multiple waves). So I think you are saying that the GCD of two or more frequencies gives a "ground" frequency of which all of them are harmonics; this is true, more or less by definition of GCD and of harmonics. When you say this GCD acts as the Tonic or key centre in musical harmony, I don't agree fully. It is true in the case of three frequencies related respectively 4:5 and 5:6, i.e., a major chord: these are three harmonics of a note two octaves below the first frequency, which indeed is the key centre for the major chord. It is not true however for three frequencies related respectively 5:4 and 6:5, i.e., a minor chord; if one seeks three integers having these successive ratios then the smallest instance is 10,12,15, which means the GCD is the frequency for which these are harmonics number 10, 12, and 15; concretely for the chord A₄,C₅,E₅ it would be F₂ a note that is not the key centre for the minor chord. Which is just to say, you should be careful to state precisely what you mean, otherwise people will not be able to understand. I'm sure there is some sense to the "Bezout's ID technique" you described, but from the given description I could not understand either what precisely is the problem to be solved, what the technique consist of, and why it solves the problem. If it is as old as you claim, then certainly it can be already found somewhere on the wikipedia, more likely in the mucic-oriented pages than in the mathematical pages. A clear description with reference to the related musical topics would be welcome. But something that is only clear to the author of the text has very little use here. Marc van Leeuwen (talk) 07:23, 29 March 2011 (UTC)

Introduction does not make sense

The following is unclear.

In addition d > 0 is their greatest common divisor and the smallest positive integer that can be written, in this form, for any integers x,y.

The first sentense says that it always holds *if* d is some common divisor, and then the above sentense says it must be the GCD, if it says anything at all. Which is it,GCD or a divisor?

(I have tidied up the other confusing language but left this. Maths articles should be intelligible to people that do not already understand the article's content before reading it!) Tuntable (talk) 03:40, 4 June 2012 (UTC)

False statement?

Hi all, I was looking for the identity and I came to this page. I believe the first statement (sentences 1 and 2) is actually false. If d is a divisor of a and b, Bezout's coefficients exist iff d is also the gcd of a and b. In particular, it is not sufficient for d to be a divisor of both a and b. As an example, you may take a = b = 4 and d = 2.

Should we change it? — Preceding unsigned comment added by Pinoeottavio (talk • contribs) 09:17, 22 June 2012 (UTC)

If you read the first paragraph carefully, you will see that it doesn't claim that Bezout's identity is satisfied for any common divisor of a and b. In the second paragraph it goes on to say that if Bezout's identity is satisfied for some common divisor d > 0 then d is the gcd of a and b. Gandalf61 (talk) 10:40, 22 June 2012 (UTC)

Proof Fixup

I really struggled with the proof, and judging from the other comments I think I'm not alone. I have trouble making heads or tails from the one on the page. I thikn it's important enough to make much more accessible. Combined with the Gandalf61's intuitive explanation, I found the one here to be excellent. Would anyone mind if I began beefing up the proof section using these resources? Garfieldnate (talk) 05:20, 8 April 2013 (UTC)

Two exercises

I never heard of Bezout's identity and I never saw a greater confusion then this article and this talk page. I think two worked out exercises + a bit of secondary school maths will summarize the whole content.

Exercise 1 : Solve the diophantin equation 6893x - 2876y = 183, x and y ε Z⁺ .

(p) Find by Euclid's algorithm GCD (6893, 2867) : 6893 - 2867•2 = 1159 ; 2867 - 1159•2 = 549 ; 1159 - 549•2 = 61 ; 549 - 61•6 = nothing. We prove that GCD (6893, 2867) = 61.

(p1) Read through the identities from right to left : 61 is a divisor 549 ---> 61 is a common divisor of 549 and 1159 ---> 61 is a common divisor 1159 and 2867 ---> 61 is a divisor of 2867 and 6893.

(p2) Read through the identities from left to right and let d be a common divisor of 6893 and 2867 ---> d is a common divisor of 2867 and 1159 ---> d is a cmmon divisor 1159 and 549 ---. d is a common divisor of 549 and 61. The properties (p1) and (p2) explain the name greatest common divisor.

(p3) Read through the identities from right to left : 61 = 1157 - 549•2 = 1157 - [2867 - 1159•2]•2 = 1157•5 - 2867•2 = [6893 - 2867•2]•5 - 2867•2 = 6893•(5) - 2867•(12) = GCD (6893, 2867).

(q) Back to our original equation 6893x - 2867y = 183. Multiply the last identity of (p3) by 3 to get 6893•(15) - 2867•(36) = 183. Conclusion : x = 15, y = 36 is the unique solution of 6893x - 2867y = 183. We were lucky GCD (6893, 2867) is a divisor of 183. If not, no solution. — Preceding unsigned comment added by C.W. Vugs (talk • contribs) 13:06, 2 May 2013 (UTC)

Exercise 2 : Solve the diophantine equation 120x + 36y = -48, x and y ε Z .

(p) Important : write the equation in such a form that we can apply Euclid's algorithm. Thus 120(-x) - 36y = 48.(Note : Euclid could subtract in a long division, but did'nt work with zero and negative numbers).

(q) Find GCD (120, 36). 120 - 36•3 = 12 ; 36 - 12•3 = nothing. Thus GCD (120, 36) = 12. Further 120•(1) - 36•(3) = 12 and also 120•(4) - 36•(12) = 48. Thus x = -4 (-x = 4) and y = 12 is a solution of 120x + 36y = -48. Again we were lucky because GCD (120, 36) is a divisor of -48. If this is not the case then no solution.

(r)If there is a solution then there are infinite many solutions because the homogeneous equation 120x + 36y = 0 or 10x + 3y = 0 has infinite many sotutions t(-3, 10), t ε Z . Therefore (x, y) = (-4, 12) + t(-3, 10) is the general solution of 120x + 36y = -48.C.W. Vugs (talk) 13:59, 2 May 2013 (UTC)

The fact that you never heard of Bezout's identity is only a witness of the utility of an encyclopedia like Wikipedia: its aim is to inform people of thing thats they do not know of. The point is that Bézout's identity is an important result which is used in many areas of mathematics. In particular it is one of the starting tools (with modular arithmetic) of Diophantine equation theory. On the other hand, the article may certainly been improved, but the lead is accurate and contains a clear statement of Bézout's lemma. If you find it confusing, this is probably because you need to read it more carefully: omitting to read some words would probably change the meaning. I recall you that Wikipedia is not a text book, and for secondary school students, its aim is to give them some relevant information that is not in their courses and their textbooks.

Your proposition of reducing the article to some working examples is not convenient: it lefts to the reader the difficult task to extract a theorem or an algorithm (that is a general and automatic method of computation) from the examples. The converse, that is using a theorem and an algorithm on an example, is much more easier to explain. Moreover the article is the target of many links, and this has to be taken into account in writing an article. D.Lazard (talk) 14:17, 2 May 2013 (UTC)

Firstly, I learned during my studies the theorem of Euclids algorithm. Here it is. (i) All a and b ε Z⁺ do have a GCD (a, b). (ii) GCD (a, a) = a. (iii) GCD (a, b) can be calculated by successive long division as an example can show. (iv) GCD (a, b) ε Z⁺ (v) GCD (a, b) is a common divisor of a and b. (vi) Each common divisor of a and b is a divisor of GCD (a, b). [properties (v) and (vi) explain the name greatest common divisor]. (vii) The diophantin equation ax - by = GCD (a, b) has an unique solution in Z⁺ x Z⁺ and this solution can also be found by Euclid's algorithm. All other statements surrounding this theorem were considered as analytic geometry and attributed to Descartes (ca. 1625), perhaps because of the fact, that he worked for long in the Netherlands. The writer of this artikel gives also two names. It is not important. C.W. Vugs (talk) 16:07, 3 May 2013 (UTC)

Secondly I read more carefully the first sentence of the article. Bezout's identity (also called Bezout's lemma) is a theorem in the elementary theory : let a and b be integers not both 0 and let d be their greatest common divisor, then there exist integers x and y such that ax + by = d. To understand this sentence one needs the following foreknowledge. (i) What is an additive group? (ii) Is Z an additive group? (iii) What is a subgroup? (iv) Form the multiples of a fixed number a a subgroup? (v) Is each supgroup in Z of this form, a set of multiples of a fixed a? (vi) Is ax + by a subgroup of Z? (vii) If this is the case does the group have a positive number? (viii) If this is the case does the group have a smallest number? (ix) Is this smallest number a common divisor of a and b? (x) Is each common divisor of a and b a divisor of d? Talking about target groups, secondary schools in the Netherlands are not interested in structure mathematics. Cambridge International Baccalaureate was not interested in theory of groups nor in numbertheory. I don't know what is the situation at the moment. Even in I.M.O. it seems to be a forbidden area, but modular arithmetic is there and instructed to selected clubs of students. In the Netherlands we have Higher Professional Education going up to a bachelor degree. They hopefully are interested in theory of groups but, when giving theory of numbers they too prefer the method based on Euclid's algorithm and to start quickly with modular arithmetic. 84.24.10.61 (talk) 14:14, 4 May 2013 (UTC)

Second sentence. In addition (i) d is the smallest positive integer that can be written as ax + by (ii) every integer of the form ax + by is a multiple of d. Is (i) and (ii) not the same?

Third sentence. x and y are called Bezout's coefficients for (a,b); they are not unique. I think the following is better : a and b are called Bezout's coefficients for the unknowns (x, y); they are unique when working in Z⁺, but there are infinite many (x, y)'s when working in Z. C.W. Vugs (talk) 15:14, 4 May 2013 (UTC)

Source for minimality claim in the intro?

In the introduction (before the contents list), it is stated:

A pair of Bézout coefficients (in fact the ones that are minimal in absolute value) can be computed by the extended Euclidean algorithm.

but no source for the minimality of the Bézout coefficients (let alone the intended meaning of minimality in absolute value for pairs of numbers) is given, nor could I find one in the article itself or the linked article on the extended Euclidean algorithm. Lambdacalculator (talk) —Preceding undated comment added 19:34, 1 November 2013 (UTC)

In fact, the extended Euclidean algorithm does not product always the minimal pair, but one of the two minimal pairs. I have corrected the assertion. For a reference, I do not know, but the reference book for this kind of results is "Knuth, The art of computer programming, Seminumerical algorithms". The proof is as follows, supposing that a and b are positive: Let $q_{i}$ and $r_{i}$ be the successive quotients and remainders in Euclidean algorithm. x and y are obtained recursively by $x_{0}=1,x_{1}=0,x_{i+1}=x_{i-1}-q_{i}x_{i}$ and $y_{0}=0,y_{1}=1,y_{i+1}=y_{i-1}-q_{i}y_{i}.$ As $r_{i-1}=r_{i+1}+q_{i}r_{i}$ and $r_{i+1}>0,$ we have $q_{i}<{\frac {r_{i-1}}{r_{i}}}.$ It follows that the $x_{i}$ and the $y_{i}$ are increasing in absolute value, change of sign at each step and are such that $\left|{\frac {x_{i}}{x_{i-1}}}\right|<q_{i}$ and $\left|{\frac {y_{i}}{y_{i-1}}}\right|<q_{i}.$ The result is obtained by taking the product of these inequalities when i varies. D.Lazard (talk) 21:48, 1 November 2013 (UTC)

"not both zero"

The article writes |x| < |b|/|d| ...

But for a = 2, b = 0, this inequality occurs |x| < 0, -- a contradiction.

May be, it is needed to require "both non-zero" ?

Mechvel (talk) 13:35, 23 January 2014 (UTC)

 Fixed D.Lazard (talk) 14:39, 23 January 2014 (UTC)

Duality

Why is this identity not considered an example of duality? It can clearly be formulated as duality in the optimization sense that the maximum of one set is the minimum of another set. Specifically, "The greatest common divisor of any two integers is equal to the smallest positive linear combination of these integers." As such, it has parallels not just to optimality duality. Once can even see connections to the duality of projective geometry where points and lines are dual as well as fourier analysis where duality is applied between points in the frequency domain and waves in the time domain (though I admit this is stretching things a little, since the identity is really only considering integer linear combinations).

It seems to me that emphasizing the dual properties of the GCD greatly clarifies the subsequent formal development of elementary number theory, as well as pointing the way to more sophisticated ideas. While this may not be a universal perspective on Bezout's identity, I would like to know why it is _wrong_. — Preceding unsigned comment added by Uscitizenjason (talk • contribs) 21:43, 29 January 2019 (UTC)

1. For being included in Wikipedia, every assertion must be sourced with reliable sources. This is a fundamental policy of Wikipedia. In this case you must provide a reliable source asserting that the term duality is commonly used in the context of Bézout's identity.
2. A duality is a correspondence between two sets (generally two sets of sets), and, here, there is only an equality between the maximum of a set and the minimum of another set. This cannot be called a duality.
3. If you were right in asserting that it is a duality, and if you were able to source this assertion, this would be not a sufficient reason for include it, as this generally does not appear in textbooks considering Bézout's identity, and it is not useful for studying Bézout's identity. D.Lazard (talk) 10:47, 30 January 2019 (UTC)

The use of the term "duality" is more general than you are acknowledging here. There is recognition at important places for the importance of duality here, and it extends to more elaborate expressions. Uscitizenjason (talk) 23:53, 11 February 2020 (UTC)

Gap in logic in the proof. We have not shown that the remainder is zero.

The proof first claims that the remainder, r, of the division a/d of the integer, a, by the minimal element, d, of S={ax+by|x,y in Z and ax+by>0} satisfies 0 <= r < d, which is clear. But it then uses the argument that "As d is the smallest positive integer in S, the remainder r is necessarily 0, as, being a remainder, it has to be less than d". This seems incomplete to me, since the remainder could be any non-negative integer less than d - not necessarily zero. The proof given at https://proofwiki.org/wiki/B%C3%A9zout%27s_Lemma, which shows that the assumption that there is an element of S indivisible by d leads to a contradiction seems far more convincing. I also think that the proof should contain more references to published proofs or described qualitatively as a sketch, not just using a mishmash of ad-libbed logic cobbled together by different users. Jamgoodman (talk) 12:41, 28 January 2020 (UTC)

"The remainder could be any non-negative integer in S ∪ {0} less than d - thus necessarily zero." (This is your sentence with my modifications in boldface). Strange that you are unable to remember the result of the preceding line. Nevertheless, I have clarified the sentence by adding some repetitions. D.Lazard (talk) 13:43, 28 January 2020 (UTC)

Structure of solutions

Concerning the following statement:

The two pairs of small Bézout's coefficients are obtained from the given one (x, y) by choosing for k in the above formula either of the two integers next to ${\frac {x}{b/d}}$.

What if $b/d$ is an integer (that is, if $b=d$, which is the case if $a=b$)? Then since $x$ is an integer, also ${\frac {x}{b/d}}$ is an integer, and the two integers next to ${\frac {x}{b/d}}$ are $x-1$ and $x+1$. One of these values is not a value for $k$ that results in

$$|x|\leq \left|{\frac {b}{d}}\right|\quad {\text{and}}\quad |y|\leq \left|{\frac {a}{d}}\right|,$$

and the wrong value should be replaced with $x$.

As an example consider $a=b=d=5$, and $(x,y)=(8,-7)$ (since $ax+by=5\cdot 8+5\cdot -7=5=d$). Then ${\frac {x}{b/d}}=8,$ and indeed

for $k=7$ we have $a\left(8-7\cdot 1\right)+b\left(-7+7\cdot 1\right)=a=d$ and $|x|=1\leq 1={\frac {b}{d}}$ and $|y|=0\leq 1=|{\frac {a}{d}}|$,

but

for $k=9$ we get $a\left(8-9\cdot 1\right)+b\left(-7+9\cdot 1\right)=-a+2b=d$, but $|x|=2\not \leq 1={\frac {b}{d}}$ and $|y|=2\not \leq 1={\frac {a}{d}}$.

For this example, we should use $k=x=8$ instead of $k=x+1=9$ to get $a\left(8-8\cdot 1\right)+b\left(-7+8\cdot 1\right)=b=d$ and $|x|=0\leq 1={\frac {b}{d}}$ and $|y|=1\leq 1=|{\frac {a}{d}}|$.

The easiest - laziest ;-) - way to correct for this would be to add the restriction that $a\neq b$. Pweemaes (talk) 12:39, 17 September 2023 (UTC)

I agree. D.Lazard (talk) 14:04, 17 September 2023 (UTC)

One correction: in the example:

...for $k=9$ we get ... $|x|=2\not \leq 1={\frac {b}{d}}$...

should be

...for $k=9$ we get ... $|x|=1\leq 1={\frac {b}{d}}$...

(but still $|y|=2\not \leq 1=|{\frac {a}{d}}|$ so $k=9$ is invalid).

Also, in addition to the suggested restriction $a\neq b$, notice that if $a=b$ then the pairs $\left(x,y\right)$ for which $|x|\leq {\frac {b}{d}}$ and $|y|\leq {\frac {a}{d}}$ are $\left(1,0\right)$ and $\left(0,1\right)$. Pweemaes (talk) 16:33, 17 September 2023 (UTC)