Is there a way to show that $\gcd(a,b) = ax + by $ without also showing that its the smallest positive linear combination? Is there a way to show that $\gcd(a,b) = ax + by$ without also showing that it is the smallest positive linear combination? i.e. Can it be shown that there exists an $a$ and $b$ such that $\gcd(a,b) = ax + by$? If there is such a proof, what is the proof?
I have seen lots of proofs for $\gcd(a,b) = ax + by$ that also shows it is the smallest but I was wondering if there was one where it did not require that too? Maybe using factorization of integers? Not 100% sure though.

If ax + by = M then gcd(a,b) divides both a and b so it divides M.  So if there are any solutions at all they must be at least as big as gcd(a,b).  The proof don't need to rely on gcd(a, b) being the smallest; just that one that small exists. 
