Take the 2-minute tour ×

Let $x$, $y$ be elements of $\mathbb{Z}$. Prove if $17\mid(2x+3y)$ then $17\mid(9x+5y)$. Can someone give advice as to what method of proof should I use for this implication? Or simply what steps to take?

share|improve this question
For a direct proof of the statement $p \rightarrow q$, you should assume that $p$ is true, and then arrive at $q$. In this case, you want to show that $17 \mid (2x + 3y) \implies 17 \mid (9x + 5y)$. So, you start by assuming that $17 \mid (2x + 3y)$ or that $\exists t \in \mathbb{Z}$ such that $2x + 3y = 17t$. Then you want to show that $\exists s \in \mathbb{Z}$ such that $(9x + 5y) = 17s$. If you can write $9x + 5y = 17k + (2x + 3y)l$, then you're done as the sum of two multiples of $17$ is again a multiple of $17&. I hope this comment, along with Don's answer resolves your question. –  JavaMan Feb 26 '13 at 15:24

4 Answers 4

So $\,\exists\;k\in\Bbb Z\,\;\;s.t.\;\;\;2x+3y=17k\,$:


$$\Longrightarrow17\mid (9x+5y)$$

share|improve this answer
I feel like the user is asking for help on writing the proof. I assume this means they are relatively new to proof writing. If that is the case, then this answer has so many bad habits that need to be addressed. First off, there is no clear assumption written. Next, it has excessive use of symbols (e.g. never use $\Rightarrow$ in writing a proof!). Lastly, it lacks words to help the reader parse what is being said. Sure it is a correct answer, but I hope the user doesn't imitate this style of writing it up in the future. –  Matt Feb 26 '13 at 17:27
What you feel is something personal, and perhaps it'd be a good idea not to talk about bad habits of others lest someone else would mention some of your own. I think you missed completely the whole point of the answer. It is supposed to give guiding lines to the OP, just as he asked. It's up to him to come up with the complete proof after seeing the above. Your comment on the very mathematical and widely used symbol $\,\Longrightarrow\,$ lacks, again, understanding of the sketchy nature of the answer, just as your mentioning the lack of words. Remember: this is not a journal paper. –  DonAntonio Feb 26 '13 at 19:31
Wow. Actually, there are a lot of very accepted standards for what constitutes good mathematical writing and what constitutes bad. The things I pointed out are not merely my opinion. Maybe you should add that this is just a sketch to your answer. I reiterate that the difference between good and bad proof writing is very difficult for new students to grasp. I'm not saying you personally have these bad habits, only that some people do have them even when writing a "full/formal" proof. I don't see what's wrong with making sure the OP doesn't mimic them when doing their own write up. –  Matt Feb 27 '13 at 0:26
I don't need to add anything of that kind to a college/university level student: it should be obvious (or else...). The things you so rudely pointed out are your opinion too, which perhaps may be shared by some other people, but I don't think you were appointed to be anyone else's speaker. Perhaps before you dare to write such a thing about somebody else's answer it'd be a good idea to surf around the site for a while and read other answers. There are all kinds: more sketchy than mine, very detailed, incomplete, complete...Everybody has his own style and you don't get to decide what's better –  DonAntonio Feb 27 '13 at 3:39
Maybe we should just eliminate all introduction to proof classes at all universities, because you seem to think all college level students magically know how to write good proofs. I've taught these classes and seen people turn in literally exactly what you wrote as a "proof." In what sense was what I wrote rude? I pointed out common mistakes that people make in introductory proof classes, which based on the tone of the question it seems this person is in. –  Matt Feb 27 '13 at 3:58

I would write the equations in $\mathbb{Z}_{17}$, which is a field, because $17$ is prime, so linear algebra applies: $$ 2x+3y=0 $$ is a linear equation of two variables, and you seek to prove that it implies $$ 9x+5y=0 $$ which means they're linearly dependent. Two equations are linearly dependent if and only if one is a multiple of the other - and this should be easy to prove.

Edit: Since you asked about proof strategy, I'd like to emphasize that this is not some random trick; the condition $p|x$ is not very nice to work with algebraically, but because $\mathbb{Z}_p$ is a field, the equivalent statement $x\equiv 0\mod p$ (I omitted the $\mod 17$ and the $\equiv$ above to make it look more like familiar algebra) is much simpler and better, because you can multiply, add and create linear spaces over $\mathbb{Z}_p$ that behave (in many ways) like real numbers.

share|improve this answer
Thinking of $\mathbb{Z}_{17}$ as a field is surely a good way to go about this, but it is not clear that the OP knows what a field is. This type of question would (most likely) arrive in a discrete math class before one would have knowledge of fields. –  JavaMan Feb 26 '13 at 15:26
@JavaMan Good point, but the field and the linear algebra are not needed if he knows how to multiply modulo, the only important part is that the second equation is a multiple of the first $\mod 17$. The reduction to linear algebra appeals more to the "proof strategy" part of the question. –  Alfonso Fernandez Feb 26 '13 at 15:35
Indeed, the vantage point of viewing $\mathbb{Z}_{17}$ as a field and knowing "linear algebra holds in a field" is not needed for this problem, and hence my comment. Algebraically manipulating equations in $\mathbb{Z}_{p}$ still does not elucidate the proof strategy, however, since the OP may still not what a field is. As you stated, the biggest component here is noticing that $9x + 5y = 17(x+y) - 4(2x + 3y)$. –  JavaMan Feb 26 '13 at 15:45

Given $17 | 2x + 3y$ then $17 | (17x + 17y) - 4(2x + 3y)$ which says $17|9x + 5y$.

share|improve this answer
using the basic rules of divisibility: that 17|17M for any M including M=x+y. and If 17|A and 17|B then 17|A-B. –  user58512 Feb 26 '13 at 15:32

$\rm\begin{eqnarray}{\bf Hint}\ \ \ a\ (cx\!+\!dy)\!\!\!\!\!\!&\ - &\rm\! c\ (ax\!+\!by)\ \ =\ \ (ad\!-\!bc)y \\ \rm thus\ \ \ \ p\mid cx\!+\!dy \!\!\!\!&\iff&\rm\!\!\! p\mid ax\!+\!by\ \ if\ \ p\mid ad\!-\!bc,\,\ p\nmid a,c,\,\ p\ prime \end{eqnarray}$

share|improve this answer

Your Answer


