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.