Let $x,y$ and $m$ be integers. Prove if $m | 4x$ + y and $m | 7x+2y$ then $m|x$ and $m|y$
Proving divisibility
3 Answers
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$.
-
2@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. – 2011-04-03
$\rm \bmod m\!:\ \begin{bmatrix} 4 & 1 \\ 7 & 2 \end{bmatrix} \begin{bmatrix}\rm x \\ \rm y\end{bmatrix} \equiv \begin{bmatrix} 0 \\ 0\end{bmatrix}\, \Rightarrow\, \begin{bmatrix}\rm x\\ \rm y\end{bmatrix} \equiv \begin{bmatrix} 0 \\ 0\end{bmatrix}\ $ since the matrix is invertible $\rm (det = 1)$
-
1That's a really good way to see it! – 2011-04-03
You can also prove this using the following theorem. It is quite useful for proving things like this. It says:
Let $a, b, c$ be integers such that $a|b$ and $a|c$ where a is not equal to 0. Then $a|(bx+cy)$ where $x$ and $y$ are integers.
By hypothesis, you have $m|(4x+y)$ and $m|(7x+2y)$. Let's show first that $m|x$. Since $m|(4x+y)$ and $m|(7x+2y)$, by the above theorem, this implies that $m|(2)(4x+y)+(-1)(7x+2y)=x$, so therefore $m|x$. To prove that $m|y$, we do the same procedure as before but with different integers. Since $m|(4x+y)$ and $m|(7x+2y)$, this implies that $m|(-7)(4x+y)+(4)(7x+2y)=y$, so therefore $m|y$. Thus, we have proved that $m|x$ and $m|y$.
I really hope this helps!