Is the below proof enough to show that the Euclidean algorithm computes the $\gcd$ for $a, b, q, r \in \mathbb{Z}$ with
$a = bq + r$ then $(a, b)=(b, r)$.
It works by showing that any common divisor of $a,b$ is also a common divisor of $b,r$, and vice-versa. If the set of common divisors of $a,b$ is the same as the set of common divisors of $b,r$, then both must have the same greatest common divisor.
Suppose that an integer $n$ divides both $a, b$.
Then, $n \mid a, b \implies \exists s,t \in \mathbb{Z}$ such that $a = ns, b = nt$.
Also, can find another linear combination: $r = a − bq = ns − ntq = n(s − tq)$.
Therefore $n|r$.Suppose that $n \mid b, r$. Then there exist suitable integers, $s, t$ with $b = sn, r = tn$.
Substituting $a = bq + r = snq + tn = n(sq + t) \implies n \mid a.$
-- If this proof is okay, then the second issue is : why does this proof not assume that there is something like $\gcd=n$ as an assumption, so that $n\mid a,b,r$.