Let $ \ a,b \in \mathbb{N}$. $ \ [(a<b)$ and $ \ (gcd(a,b) \neq a)] \implies [gcd(a,b) < a]$

Question

Question:

Is the following statement true:

Let $ \ a,b \in \mathbb{N}$. $ \ [(a<b)$ and $ \ (gcd(a,b) \neq a)] \implies [gcd(a,b) < a]$

I cannot think of any counter example. I think the statement is true.

Answer 1

Yes. The greatest common divisor of $a$ and $b$ is always a divisor of both $a$ and $b$, and for any divisor $d$ of $a$ we have $d\leq a$. Thus we have $\gcd(a, b) \leq a$, and since $\gcd(a, b) \neq a$ we also have $\gcd(a, b) < a$.

Answer 2

If $c=gcd(a,b)>a$, then $c|a$, but then we got that $c\le a$, therefore $c>a$ is an absurd.

Answer 3

With $a<b, \gcd (a,b) = \gcd (a,b-a)$

if $a = b-a$ then $gcd(a,b) = a$ which would contrdict our assumptions.

if $a < b-a$ we can subtract another $a$

$\exists n\in \mathbb N: 0<(b-an) < a$

$\gcd (a,b-an) \le b-an$

This is essentially the Euclidean Algorithm.