2
$\begingroup$

I'm trying to understand the detailed logic structure of a proof by use of the bezout identity.The number theoretic part i easily understand, the problem i'm having is with the logic.

One example :

Proposition- gcd(a,b)= gcd( gcd(a,b) , b) .
I understand this perfectly by intution, and i can also prove by showing that every integer d that divides a and b, must divide gcd(a,b) and b , also the converse , proving they have same common divisors and hence same gcd.
My problem is completely understanding every step of a formal proof of that proposition, by use of the bezout identty.
I know bezout identity allows us to infer two statements :

  • Statement 1 : There exists x,y in Z s.t ax + by = gcd(a,b) = d .
  • Statement 2 : There exists xo,yo in Z s.t gcd(a,b).xo + b.yo = gcd( gcd(a,b) , b ) = w

Now, how should we proceed to prove the proposition, that is, to prove d=w ?

1 - Should we try to prove that statement 1 is true if and only if statement 2 is true ? ( i guess not )

2 - Could i simply find some pair xo,yo, namely xo=1 and yo=0, which makes w=d ? Would that entirely prove the Proposition ?

3 - If it's enough to prove the entire proposition, is that the only option to prove by the use of bezout identity ( proving w=d ) ? Because in more complicated statements ( like gcd(a,b) = gcd(a+bx,b) ) , i might not be able to guess right away the xo,yo that makes w=d.

Thanks a lot in advance.

$\endgroup$
2
$\begingroup$

I think your main difficulty is that you have only really stated part of Bezout's result. The full version is:

if $m,n,c$ are integers, then there exist integers $x,y$ such that $mx+ny=c$ if and only if $c$ is a multiple of $\gcd(m,n)$.

So for your question: let $d=\gcd(a,b)$ and $w=\gcd(d,b)$. Then there exist $x_1,y_1$ such that $ax_1+by_1=d$, and there exist $x_2,y_2$ such that $dx_2+by_2=w$. Substituting the first equation into the second and rearranging, $$a(x_1x_2)+b(y_1x_2+y_2)=w\ ,$$ and since the two expressions in brackets are integers, we have $\gcd(a,b)\mid w$, that is, $d\mid w$. On the other hand, the equation $$dx+by=d$$ obviously has the integer solution $x=1$, $y=0$, and so $\gcd(d,b)\mid d$, that is, $w\mid d$. This completes the proof.

$\endgroup$
  • $\begingroup$ But all possibles linear combinations mx + ny using x,y integers gives us a multiple of gcd(m,n), no matter how we choose x,y. $\endgroup$ – nerdy Apr 7 '14 at 13:40
  • $\begingroup$ Yes, that's exactly the point. That is how I proved $d\mid w$. $\endgroup$ – David Apr 7 '14 at 13:55
  • $\begingroup$ Yeah, but just saying that we dont need to add that "if and only if" part, because c is always a multiple of gcd(m,n).Thanks for the input ! $\endgroup$ – nerdy Apr 7 '14 at 14:00
  • $\begingroup$ No, we do need the "if and only if" - the deduction in my previous comment uses the "only if", but we need the "if" right at the start to get the equations $ax_1+by_1=d$ and $dx_2+by_2=w$. $\endgroup$ – David Apr 7 '14 at 14:21
1
$\begingroup$

Hint $\ $ By repeatedly applying $\,\ (m,n)\,\Bbb Z\, =\, m\,\Bbb Z + n\,\Bbb Z\,\ $ we obtain

$$\begin{eqnarray} ((a,\,b),\,bc)\,\Bbb Z &\,=\,& (a,\,b)\,\Bbb Z + bc\,\Bbb Z\\ &=& (a\,\Bbb Z+b\,\Bbb Z)+bc\,\Bbb Z\\ &=& a\,\Bbb Z+(b\,\Bbb Z\,+\,bc\,\Bbb Z)\\ &=& a\,\Bbb Z +\, b\,\Bbb Z\,\ {\rm by}\,\ bc\,\Bbb Z\subseteq b\,\Bbb Z\\ &=& (a,\,b)\,\Bbb Z\end{eqnarray}\quad\ \ $$

Your question is the special case $\ c = 1.$

$\endgroup$
0
$\begingroup$

The technique that I use to prove statements like that is taking $d=\gcd (a,b)$ and proving that $d$ divides $\gcd(a,b)$ (which is obvious) and that $d$ divides $b$ (which is rather obvious, too).

Conversely, take $d'=\gcd(\gcd(a,b),b)$. Note that we have already proved that $d$ divides $d'$ since $d$ is a common divisor of $\gcd(a,b)$ and $b$. You are to prove that $d'$ divides $a$ and $b$. But this is also obvious, since $d'$ divides $\gcd(a,b)$. Hence, $d'$ divides $d$ and $d=d'$.

In find this technique is much easier that messing up with Bezout's identity.

$\endgroup$
  • 1
    $\begingroup$ Again, this is exactly the proof i said i understood already :D. But thanks for trying to help $\endgroup$ – nerdy Apr 7 '14 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.