1
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry for nitpicking. But to be more precise, maybe this answer should stress that we are talking about set of natural numbers or positive integers which are integer combinations of $a$ and $b$. Or the possibility $d=\pm\gcd(a,b)$should be included, if we allow negative integers, too. $\endgroup$ – Martin Sleziak Jan 17 '16 at 7:16
  • $\begingroup$ @Martin: Good point; I made a small change to cover it. $\endgroup$ – Brian M. Scott Jan 17 '16 at 7: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.