# $\gcd(a,b)$ is the least positive linear combination of $a$ and $b$

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

• 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

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.