Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients?

Question

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients? i.e. there exists two integers $i_0,i_1 \in \Bbb Z$ st. $d=i_0a_0+i_1a_1$.

I know this is true if $d$ is the greatest common divisor, see http://sites.millersville.edu/bikenaga/abstract-algebra-1/euclid/euclid.html. But I don't know if it holds if $d$ is just a common divisor. Can anyone give a proof or provide a counter example?

Thank you!

Answer 1

A counter-example:

Consider $8$ and $12$. Their g.c.d. is $4$, and $4$ is clearly a linear combination of them, being $-1 \cdot 8 + 1 \cdot 12$.

However, note that $2$ is a common divisor, but since $8$ and $12$ are both $0$ mod $4$, any linear combination thereof must also be $0$ mod $4$, so that in particular, $2$ (which is, of course, $2$ mod $4$) cannot be a linear combination of $8$ and $12$.

Answer 2

In fact the proof of Bezout’s identity given in Wikipedia shows that the set of integer combinations of $a$ and $b$ is precisely the set of integer multiples of their greatest common divisor, so if $d$ is a common divisor of $a$ and $b$, and $|d|\ne\gcd(a,b)$, then $d$ is definitely not an integer combination of $a$ and $b$.