Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
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
1  
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
1  
@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
1  
Thanks guys! I got it now! it's so obvious once you get it –  Arvin Apr 3 '11 at 15:42
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. –  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$)

share|improve this answer
    
That's a really good way to see it! –  quanta Apr 3 '11 at 17:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.