# Proof for any smaller common divisor than g.c.d. being not a linear combination

In linear combinations, the basic property is if there are two integer quantities, say $a$ and $d$, then any integer multiplied to the two will again lead to an integer; i.e. $ax + dy, \forall a,b,x,y \in \mathbb{Z}$ is also an integer. This is based on the closure of integers w.r.t. addition.

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, 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, \exists n,m \in \mathbb {Z}$. So, $d = qa + r => c(n-m) = r$. Also, $n \ge m$ as $d \ge a$. So, $c\mid 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\mid d$ & $c \mid qa$; then $c \mid (d -qa)$, and hence $c \mid 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$.

Let $g$ be the greatest common divisor of $a$ and $b$. If $d=ax+by$ for some integers $x$ and $y$, then $g$ divides $d=ax+by$, and hence $g\le d$.
• I am talking something different, if not wrong. Let me elaborate it : Say, $35$ and $140$; here, common divisors (not linear combinations) are : $5, 7$. Here, these two are not a linear combination, and so not g.c.d. These must be less than g.c.d., as g.c.d is the greatest common divisor. How to prove that such divisors are less than gcd, is the issue. – jiten Nov 28 '17 at 10:07
• I showed that if $d$ is a linear combination, then it is greater than $\gcd$. This is equivalent with saying that if $d$ is less than $\gcd$ then it is not a linear combination. So any common divisor that is less than $\gcd$ is not a linear combination. Hope this clarifies your doubt. – awllower Nov 28 '17 at 10:10