This is in reference to the same proof given in the post
Is greatest common divisor of two numbers really their smallest linear combination?
I couldn't add a comment there so I'm asking it here. I am trying to understanding the same proof but can't digest a fact.
The part that d <= gcd(a,b) is understandable coz g in gcd implies greatest, so d can only be less than/equal to gcd(a,b). ( Fact -1)
The other part says that as gcd(a,b) | sa + tb then gcd(a,b) | d. This is the part where I am getting confused.
Ques: Fact 2 -> m | sa + tb is true and gcd(a,b) | sa + tb is also true.
Now we could write gcd(a,b) | m or m | gcd(a,b). I can well reason that as gcd(a,b) >= m , so m |gcd(a,b) is possible but I can't reason why we can write gcd(a,b) | m knowing until as of now that gcd(a,b) can be > = m. if gcd is greater than m then the result will not be an integer ?
Can anyone explain with some logic ? Would be really helpful.
Thanks in Advance
Ankit