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.
On
Let's revise the definition of GCD.
Let $a, b$ be integers with at least one of them being non-zero. A positive integer $d$ is said to be the GCD of $a$ and $b$ and denoted by $d = (a, b)$
Let $b$ be the non-zero integer out of $a$ and $b$. It is easy to show that there exist unique integers $q, r$ such that $a = bq + r$ where $0 \leq r < |b|$ and then further show that $(a, b) = (b, r)$.
This is the euclidean algorithm to find GCD of $a, b$. Applying this algorithm we get remainders $r_{1}, r_{2}, \dots, r_{n}$ such that $r_{n} = 0$ and then $r_{n - 1}$ is the the GCD of $a, b$. We have the relations $$a = bq_{1} + r_{1}, b = r_{1}q_{2} + r_{2}, \cdots r_{i - 2} = r_{i - 1}q_{i} + r_{i}$$ From these relations we can get $ r_{n - 1} = ax + yb$ with $x, y$ being integers. A numerical example should help to explain this clearly.
Let $ a = 21, b = 15$. Then we have $$21 = 1\cdot 15 + 6, 15 = 2\cdot 6 + 3, 6 = 2\cdot 3 + 0$$ so that $3$ is the GCD. And doing back calculation we get $$3 = 15 - 2\cdot 6 = 15 - 2(21 - 1\cdot 15) = 3\cdot 15 + (-2)\cdot 21 = 15x + 21y$$ where $x = 3, y = -2$.
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.