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