Let $x,y,z$ be integers and $11$ divides $7x+2y-5z$. Show that $11$ divides $3x-7y+12z$.

I know a method to solve this problem which is to write into $A(7x+2y-5z)+11(B)=C(3x-7y+12z)$, where A is any integer, B is any integer expression, and C is any integer coprime with $11$.

I have tried a few trials for example $(7x+2y-5z)+ 11(x...)=6(3x-7y+12z)$, but it doesn't seem to work. My question is are there any tricks or algorithms for quicker way besides trials and errors? Such as by observing some hidden hints or etc?

I am always weak at this type of problems where we need to make smart guess or gain some insight from a pool of possibilities? Any help will be greatly appreciated. And maybe some tips to solve these types of problems.

Thanks very much!


Let $n=3x-7y+12z$. Since there exsits an $m\in\mathbb Z$ such that $$7x+2y-5z=11m,$$ We have the following two :

$$7n=21x-49y+84z$$ $$33m=21x+6y-15z$$ Then, we have $$7n-33m=-55y+99z\Rightarrow 7n=33m-55y+99z=11(3m-5y+9z).$$ Since we know $7$ and $11$ are coprime, we know that $n$ is a multiple of $11$.


The easiest way can be : eliminate one of the three variables like below


$$\iff 7(3x-7y+12z)=3(7x+2y-5z)-11(5y-9z)$$

If $\displaystyle 11$ divides $\displaystyle 7x+2y-5z,11$ will divide $\displaystyle7(3x-7y+12z)$

But $(7,11)=1$

  • $\begingroup$ Congruences would be very useful, but I don't know if we can use them... $\endgroup$ – chubakueno Dec 21 '13 at 2:29
  • $\begingroup$ @chubakueno, definitely, if $\displaystyle 11$ divides $\displaystyle 7x+2y-5z, 7x+2y-5z\equiv0\pmod{11}$ $\displaystyle\implies 3(7x+2y-5z)-11(5y-9z)\equiv0\pmod{11}$ $\displaystyle\iff7(3x-7y+12z)\equiv0\implies3x-7y+12z\equiv0 $ as $(7,11)=1$, But I did not use this in the answer as Congruence may not have been taught yet $\endgroup$ – lab bhattacharjee Dec 21 '13 at 7:03

Hint $\ $ Scale the first sum so that, mod $11,\,$ its $\,y$ coefficient $\,\color{#0a0}2\,$ becomes that of the second sum, i.e. $\,\color{#c00}{-7\equiv 4}.\,$ So we need to multiply by $\rm\,\color{orange}{by\ 2}\,$ to scale from $\,\color{#0a0}2$ to $\,\color{#c00}4.\,$ Doing so we obtain

$$\begin{eqnarray}{\rm mod}\ 11\!:\,\ 0&\equiv&\ \, 7x\!+\!\color{#0a0}2y\!-\!5z \\ \overset{\color{orange}{\times\ 2}}\Rightarrow\ 0&\equiv& 14x\!+\!4y\!-\!10z \\ &\overset{\phantom{2}}\equiv&\ \, 3x\!\color{#c00}{-\!7}y\!+\!12z \end{eqnarray}\qquad\qquad $$

Remark $\ $ The converse holds also since $\,11\mid 2n\iff 11\mid n$. I picked the smallest coefficient $\,\color{#0a0}2\,$ because generally that will be easiest to divide by (or invert). In fact, it is very easy to divide by $2$ mod odd $\,m,\,$ since one of $\ n\equiv n+m\,$ is even; e.g. as above $\,\color{#c00} -7\equiv -7+11 = 4\,$ is even, hence $\rm\,\color{#c00}{-7}/\color{#0a0}2 \equiv 4/2 \equiv \color{orange}2.$


$ 7x+2y-5z \equiv 14x +4y-10z \equiv(4-1)x+(4-11)y-(0-1)z\equiv 3x-7y+z$ $ \equiv3x-7y+12z $ (mod 11)


Your Answer

