# Logical structure of elementary number theoretic proof

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.

## 3 Answers

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.

• 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. – nerdy Apr 7 '14 at 13:40
• Yes, that's exactly the point. That is how I proved $d\mid w$. – David Apr 7 '14 at 13:55
• 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 ! – nerdy Apr 7 '14 at 14:00
• 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$. – David Apr 7 '14 at 14:21

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.$

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.

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