In g.c.d. computation of d = qa + r, with d(dividend), a(divisor), q(quotient), r(remainder), there may be many common divisors but if smaller than g.c.d., then not a linear combination of a and r.

I am unable to make a proof for the above, that is rigorous and directly addresses the issue rather than contradiction based approach, as the below attempt shows the failure of my rigorous approach.

If c is a common divisor of d and a, then d=nc, a=mc, ∃n,m∈Z. So, d=qa+r => c(n−m)=r. Also, n≥m as d≥a. So, c∣r also. Alternately, the divisibility of r by c can be derived by the linear combination: r=d−qa, i.e. if the linear combination c∣d & c∣qa; then c∣(d−qa), and hence c∣r.

Also, gcd will make use of two linear combinations at each step: (i) d=qa+r, (ii) r=d−qa. By (i), any common divisor d′ of a & r is also a divisor of d. Similarly, by (ii) the same common divisor d′ of d and a is also a divisor of r.