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.

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)$ 


*

*if $d \mid a, d \mid b$

*if there is any integer $c$ with $c \mid a, c \mid b$ then $d \mid c$
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$.
