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

Hope this helps.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – jiten Nov 28 '17 at 10:07
  • $\begingroup$ 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. $\endgroup$ – awllower Nov 28 '17 at 10:10
  • $\begingroup$ A more rigorous proof that directly handles such common divisors, which are lesser than gcd; and shows that they are not linear combinations, is my need. $\endgroup$ – jiten Nov 28 '17 at 10:14
  • $\begingroup$ So which part of the proof do you think is not rigorous enough? Thanks for the feedback. $\endgroup$ – awllower Nov 28 '17 at 10:16
  • $\begingroup$ The part which makes the equivalence. It is not direct, or rigorous approach according to me. I need a different approach, definitely. Is it not possible to have direct approach and rigor both. $\endgroup$ – jiten Nov 28 '17 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.