# Divisibility proof involving substitution

I’m having trouble with the proving the following:

If $a \mid b-2c$ and and $a \mid 2b+3c$ then $a \mid b$ and $a \mid c$.

Heres my partial solution:

By definition of divisibility, $b-2c=ak$ (for some $k\in\mathbb{Z}$) and $2b+3c=am$ (for some $m\in\mathbb{Z}$)

Then $b=ak+2c$: substituting into the other equation yields $2(ak+2c)+3c=am$. This means $2ak+7c=am$

I’m not sure where to go from here. Any help would be great :)

-
Provided $(a, 7)=1$. Then it is correct! –  PAD Jul 13 '12 at 21:42

Rearrange the equation $2ak+7c=am$ to get $7c=a(m-2k)$, showing that $a\mid 7c$. Note that while this would certainly be true if $a\mid c$, it would also be true if $a=7$, regardless of what $c$ might be. This suggests that we should go back to the original question and see what happens when $a=7$. In that case we have $7\mid b-2c$ and $7\mid 2b+3c$. Can this be true without having $7\mid b$ and $7\mid c$?

Equivalently, is there a solution other than $b\equiv c\equiv 0\pmod7$ to the system

\left\{\begin{align*}&b-2c\equiv 0\pmod7\\&2b+3c\equiv 0\pmod7\;?\end{align*}\right.

Mod $7$ the second congruence is actually just twice the first, since $-4\equiv 3\pmod 7$. Thus, the congruences are not independent, and any solution to the first must also be a solution to the second. It’s not hard to find a non-zero solution to the first congruence.

-

Hint $\rm\ mod\ a\!:\, b\equiv 2c,\ 3c\equiv -2b \equiv -4c\,\Rightarrow\, 7c\equiv 0.\,$ So $\rm\, \rm\color{#C00}{if\ \ 7\nmid a\ \ then}\,$ $\rm\,c\equiv0\,\Rightarrow\,b\equiv 2c\equiv 0.$

$\rm\color{#C00}{It\ fails\ if\,\ 7\:|\:a.}$ If $\rm\:a = 7c,\,$ let $\rm\:b = 2c.\:$ So $\rm\:a\:|\:b\!-\!2c = 0,\ a=7c\:|\:2b\!+\!3c = 7c,\,$ but $\rm\:a=7c\nmid c.$

Remark $\$ Geometrically the result says that, modulo $\rm\:a,\:$ the lines $\rm\: y = 2x,\ 2y = -3x\:$ intersect only at the origin if $\rm\:7\nmid a,\:$ but otherwise they intersect elsewhere too, e.g. mod $7$ the lines coincide since $\rm\:2y = - 3x = 4x,\,$ so $\rm\:y = 2x\:$ by scaling by $4 \equiv 1/2$. Thus, being identical, their intersection is the entire line $\rm\:y = 2x,\:$ i.e. the $7$ points $\rm\:(x,2x)\ mod\ 7.$

If you know linear algebra, note that the system $\rm\:2x-y = 0 = 3x+2y\:$ has determinant $7.\,$ So if $7$ is coprime to $\rm\,a,\,$ then $7$ is invertible mod $\rm\,a,\,$ so we can use Cramer's rule to infer $\rm\:(x,y) = (0,0).$

-

When you get to $b−2c=ak$ and $2b+3c=am$, the next thing to do is to see if you can eliminate $b$ between these equations. That should allow you to show that $c$ is an expression with a factor of $a$. I will explain more if you need more of a hint.

Edit: Ah - I was assuming that the question itself was correct!

-

This is not always true. For example, let $a=7$, $b=9$, $c=1$.

One can show that the only counterexamples involve $a$ being a multiple of $7$.

Remark: One view of things is that the reason for the failure is the fact that the determinant of the matrix $$\begin{pmatrix} 1 &-2\\2 &3\end{pmatrix}$$ is divisible by $7$. In a problem of this type, we can conclude the divisibility only when the determinant of the matrix is equal to $\pm 1$.

For example, if we replace $b-2c$ by $b+2c$, then the desired divisibility result will hold. So a slightly different question may have been intended.

-