# Homework Help: Need help on a implication proof

1. Feb 20, 2010

### Melodia

1. The problem statement, all variables and given/known data
Hi everyone, I need help on proving or disproving this:

Please just show me how to do one of them, and I'd like to try to do the rest on my own. If I don't know then I will post more questions here.

2. Relevant equations

3. The attempt at a solution
So far, I've interpreted this question this way:
i) for all natural numbers n, {there exists natural number j so that m = 5j + 3 and there exists natural number k so that n = 5k + 4, which works for all natural number m} implies that there exists natural number i so that the product mn = 5i + 2
ii) for all natural numbers m, {there exists natural number i so that m = 5i + 2 and there exists natural number k so that n = 5k + 4, which works for all natural number n} implies that there exists natural number j so that the product mn = 5j + 3
iii) for all natural numbers m, {there exists natural number i so that m = 5i + 2 and there exists natural number j so that n = 5j + 3, which works for all natural number n} implies that there exists natural number k so that the product mn = 5k + 4

But this seems so confusing to me, if anyone could point me in the right direction and show me how to do one of those it would be great!

2. Feb 20, 2010

### Dick

Ok, I think you're interpreting them correctly. Let's try the first one. You've got m=(5j+3) and n=(5k+4). mn=(5j+3)(5k+4). Multiply that out and see if you can write it as 5*(something)+2.

Last edited: Feb 20, 2010
3. Feb 20, 2010

### Melodia

Code (Text):
Assume n and m are natural numbers:
Assume there exists a natural number j and natural number k:
Assume:
mn = (5j + 3)(5k + 4):
= 25jk + 20j + 15k + 12
= 5(5jk + 4j + 3k) + 12
let i = 5jk + 4j + 3k
mn = 5i + 12
Then mn does not equal 5i + 2
Then m = 5j + 3 and n = 5k + 4
Then V(m) and W(n) together does not imply U(mn)
That is what I have so far for the first one "i)".
It doesn't look right to me though. :x

4. Feb 21, 2010

### Dick

You haven't taken all of the fives out yet. 5i+12=5i+10+2=5i+5*2+2=5(i+2)+2.

5. Feb 21, 2010

### Melodia

Oh! I got it now thanks.
But there's one more problem:
In the "i)", it says "for all n, ...., which works for all m", and the rest are "for all m, ...., which works for all n"; notice that the n and m are switched. Wouldn't that affect the answer?

6. Feb 21, 2010

### Dick

No. "all n and all m" is the same thing as "all m and all n". BTW not all of those are true. For any ones that aren't you just have to find an example of an n and m for which it's not true.

7. Feb 21, 2010

### Melodia

(Lol I just found that you could write symbols with the LaTeX feature)
Oh I see. But if one of the symbols switched to the $$\exists$$ (there exists one or more), then it would mean different things right?
And here is what I have so far, the "iii)" is disproved:

Last edited: Feb 21, 2010
8. Feb 21, 2010

### Dick

Yeah, just use TeX. I'm having a hard time flipping through your "Code" frames. But I think you've got it right. (i) and (ii) are true. (iii) is not. mn=5k+4 and mn=5k+6 can't be true at the same time. Because 6-4 isn't divisible by 5. To put it more simply if you pick m=2 and n=3 then mn=6 doesn't have the form 5k+4.

9. Feb 21, 2010

### Melodia

Oh sorry I changed to quote tags ^^