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.

  • 1
    $\begingroup$ Any divisor of the gcd is a common divisor. $\endgroup$ – Gerry Myerson Nov 29 '17 at 8:44
  • $\begingroup$ Please see edit to my OP. $\endgroup$ – 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$.

  • $\begingroup$ It seems that g.c.d. being the smallest positive linear combination is a theorem to be used for proving my result. If yes, then even a simpler proof based on contradiction, would work; that simply states that if smaller than g.c.d. then the common divisor is not a linear combination. This also means that my proof is not only uselessly long one, but also flawed one if it does not use the stated property of g.c.d. $\endgroup$ – jiten Dec 1 '17 at 5:42
  • $\begingroup$ "It seems that g.c.d. being the smallest positive linear combination is a theorem to be used for proving my result." And how is anybody supposed to guess, from the way you posted your question, that you are supposed to, or even allowed to, use that fact about the gcd? But what my argument does, is it proves that the gcd is the smallest positive linear combination, without assuming it. $\endgroup$ – Gerry Myerson Dec 1 '17 at 7:46
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ So, you mean to say that the proof for g.c.d. being the smallest positive linear combination, is a prerequisite for this proof. Without that my proof is bland and meaningless. So, my proof essentially shows that my approach is wrong, as any proof depends on g.c.d. for contradiction based proof. Hence, there is no need for such proof, and a simple proof based on contradiction that states that if smaller than g.c.d., then the common divisor is not a linear combination is okay. $\endgroup$ – jiten Nov 30 '17 at 9: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.