# How to prove if there are common divisor(s) smaller than GCD, they are not linear combinations

I want to prove that if there are possibly divisors smaller than g.c.d., they are not linear combinations of the integers involved.

If $c$ is a common divisor, then $a = cx, b= cy, \exists x,y \in \mathbb {Z}$. Then, $c$ is a divisor of the linear combination $cx + cy$. Here is the fallacy, as how can I mathematically say that a gcd is a linear combination, but not $c$.

My logic goes as follows:

As earlier stated, $a = cx , b = cy$. So, need find new multipliers, say $\exists e,f \in \mathbb {Z}$ to prove that $c = e.c.x + f.c.y$ is a linear combination.

This equation can be reduced to, for $c \ne 0$:

$1 = ex + fy$

So, the options are :

(i) $ex = 1, fy =0$ $=>$ both $e = \pm 1$,& $x = \pm 1$, and either $f=0$, or $y =0$

(ii) $ex = 0, fy =1$ $=>$ both $f = \pm 1$, & $y = \pm 1$, and either $e=0$, or $x =0$

But, $x,y \ne 1$, as these are the multipliers needed to equate $c$ to $a, b$ respectively.

Broke it! Really?

I request vetting of my proof.

• Any divisor of the gcd is a common divisor. – Gerry Myerson Nov 29 '17 at 8:44
• Please see edit to my OP. – jiten Nov 29 '17 at 10:35

You want to show that if $0<c<d=\gcd(r,s)$ then there do not exist $m,n$ such that $mr+ns=c$. Well, $r=du$ for some integer $u$, and $s=dv$ for some integer $v$, so $mr+ns=mdu+ndv=(mu+nv)d$ is a multiple of $d$. But $0<c<d$ implies $c$ is not a multiple of $d$. So $mr+ns$ can't be $c$.
• I still am adamant that my proof is flawed as it can be applied to $\gcd$ too, and the reason is not taking into account the properties of the $\gcd$. Above all, this error would go away at once, if I accept the $\gcd's$ stated property as an axiom / assumption. Hence, no need to make a big proof and a one-liner based on contradiction is equally fine. – jiten Dec 4 '17 at 13:07
The reduction to showing that $1 = ex + fy$ is fine. The next step is to simply note that $x$ and $y$ have a common divisor $d$ (= $\gcd(x,y)/c \neq 1$). Since $d$ divides $x,y$, it divides $1 = ex+fy$ which is a contradiction.