Let $l$ be the smallest positive linear combination of $a,b\in \mathbb{Z}^+$ i.e.,$$l := \min\{ax+by >0 : x,y\in\mathbb{Z}\}.$$ Now, according to @Brahadeesh's answer here, Proof for $\gcd$ being the smallest linear combination of $a,b \in \mathbb {Z}$., we can show that $l\mid a$ and $l\mid b$ (simultaneously).

But, consider $k>l$ such that $k\in \{ax+by >0 : x,y\in\mathbb{Z}\}$. Then, is it possible to show that $k\not\mid a $ and $k\not\mid b$ (simultaneously)? This indirectly gives us that there are no common divisors of $a$ and $b$ that are greater than $l$ which then proves that $l = \gcd(a,b)$.

The direct proof of the fact that $l=\gcd(a,b)$ would be to show that $c\mid a $ and $c\mid b \; \Rightarrow \; c\mid l$, which is quite trivial from the definition of $l$. However, I don't want to make use of this fact and instead want to show that

Claim: If $k>l$ such that $k\in \{ax+by >0 : x,y\in\mathbb{Z}\}$ then $k\not\mid a $ and $k\not\mid b$ (simultaneously).

Thanks in advance.

  • 1
    I assume what you actually want here is that $k$ does not divide both $a$ and $b$ (but could divide one or the other). – user7530 Dec 7 '17 at 8:48
  • @user7530 Yes that is true, should I remove the word simultaneously from the question? – Vidit D Dec 7 '17 at 9:00
  • some other proofs there math.stackexchange.com/questions/2215445/… – zwim Dec 7 '17 at 9:09
  • @zwim i don’t think this really answers the OP’s question. It seems that they already know of the standard way to prove that $\gcd$ is the smallest positive linear combination. – Brahadeesh Dec 7 '17 at 9:24
up vote 3 down vote accepted

I’m not sure that there’s much difference between what you want and the “direct” proof. I would argue as follows. Suppose for contradiction that $k\vert a$ and $k\vert b$. Then $k\vert l$, and by an identical argument $l\vert k$. Therefore $k=l \not> l,$ a contradiction.

Since the g.c.d. is in the form:

$$l=ax+by$$

Every other $k>l$ in the form:

$$k=ax'+by'$$

is a multiple of $l$,

thus it can't divide a and b simultaneously.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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