# Proving divisibility

Let $x,y$ and $m$ be integers. Prove if $m | 4x$ + y and $m | 7x+2y$ then $m|x$ and $m|y$

-

Let $u = 4x + y$ and $v = 7x + 2y$ so that $x = 2u - v$ and $y = 4v - 7u$.

Since $m | u$ and $m | v$ it also happens that $m | 2u - v$ and $m | 4v - 7u$.

That proves that $m | x$ and $m | y$.

-
Thanks, but how did you get x = 2u - v and y = 4v - 7u?? I can't see how you got those – Arvin Apr 3 '11 at 15:30
Well u has 4x in it and v has 7x in it. So 2u - v will just have 1x in it. I was lucky and the ys cancelled out. Since I have x = something I could easily find y. This is called Gaussian elimination. – quanta Apr 3 '11 at 15:36
@Arvin: I'm not quanta but I'll take the liberty of trying to demistify it: We have $u = 4x + y \Rightarrow 2u = 8x + 2y$ We also have $v = 7x + 2y$, we we now subtract the this equation from above one $2u - v = 8x + 2y - 7x - 2y \Rightarrow 2u - v = x$ Similarly for the other one. – user5501 Apr 3 '11 at 15:36
Thanks guys! I got it now! it's so obvious once you get it – Arvin Apr 3 '11 at 15:42
@Arvin: A simple way to see how the above equations arise is to use the matrix form in my answer. They arise from solving $\rm\ M\ \vec x = \vec u\$ so $\rm \vec x = M^{-1}\ \vec u\$ where $\rm\:M\:$ is the matrix in my answer. But it's simpler to use $\rm\ \vec u = \vec 0\$ as in my answer. – Bill Dubuque Apr 3 '11 at 17:16

$\rm\: mod\ m:\ \begin{pmatrix} 4 & 1 \\\\ 7 & 2 \end{pmatrix} \begin{pmatrix} X \\\\ \rm Y\end{pmatrix}\ \equiv\ \begin{pmatrix} 0 \\\\ 0\end{pmatrix}\ \Rightarrow\ \begin{pmatrix} X \\\\ \rm Y\end{pmatrix}\ \equiv\ \begin{pmatrix} 0 \\\\ 0\end{pmatrix}\$ since the matrix is invertible ($\rm det = 1$)

-
That's a really good way to see it! – quanta Apr 3 '11 at 17:26