# Homework Help: Prove This!

1. Feb 8, 2005

### CollectiveRocker

I'm given the statement: if m^2 is of the form 4k+3, then m is of the form 4k+3. I don't even know how to begin proving this. I'm guessing by contraposition. I really have a great deal of difficulty with proofs in general; whether I can't see ahead in written steps, I don't know. I can do calculus and differential equations fine, but proofs are a whole different story.

2. Feb 8, 2005

### MathStudent

Yes, I would prove the contrapositive, that is - if m is not of the form 4k +3 then m^2 is not of the form
4k +3.

hint: if m is not of the form 4k+3, then it is either 4k, 4k + 1, or 4k + 2.

3. Feb 8, 2005

### CollectiveRocker

Hold the phone. Now I'm totally confused.

4. Feb 8, 2005

### MathStudent

do you agree that the statement I wrote above is the contrapositive?

5. Feb 8, 2005

### CollectiveRocker

Kinda,
why wouldn't it be something like 2k + 3?

6. Feb 8, 2005

### primarygun

For any positive integer k, m^2 only can be expressed in 4k, 4k+1 , 4k+2.
Why don't you try to prove that m^2 cannot be expressed in form of 4k+3 or 4k-1?)

7. Feb 8, 2005

### CollectiveRocker

I don't even know how to start. How do you recommend proving that?

8. Feb 8, 2005

### primarygun

Let me explain your mind first in order to show that I totally understand what your want is.
For m^2 , an integer can be expressed into 4k+3. then , m can be expressed into 4n+3.
Where k and n are integers, right?

9. Feb 8, 2005

### MathStudent

if p and q represent statements, then for a conditional statement like
if p then q

the contrapositive would be:
if not q then not p

in this case, p is: "m^2 is of the form 4k + 3"
and q is: "m is of the form 4k + 3"

not p (also written as ~p or p' ) is just the negation of p which is "m^2 is not of the form mk + 3"

and the negation of q is: "m is not of the form 4k + 3"

the contrapositive is therefore:
if m is not of the form 4k + 3 then m^2 is not of the from 4k +3

realize that every integer can be written in one of the following forms:
4k, 4k+1, 4k+2, 4k+3,

therefore an equivalent way of saying "m is not of the form 4k+3" is to say
"m is of the form of either 4k, 4k+1, or 4k+2"

Thus the contrapositive becomes
if m is of the form of 4k, 4k+1, or 4k+2 then m^2 is of the form of 4k, 4k+1, or 4k+2

your proof now has three cases you need to show:
case1: if m is of the form 4k, then m^2
case2: if m is of the form 4k+1 then m^2
case3: if m is of the form 4k+2 then m^2

edit: each of the cases needs to show that m^2 is of either of the forms 4k or 4k+1 or 4k+2

Last edited: Feb 9, 2005
10. Feb 8, 2005

### CollectiveRocker

How do you prove case 1?

11. Feb 8, 2005

### primarygun

Using mod or just simply square it.

12. Feb 8, 2005

### MathStudent

$$m = 4k$$ where k is an integer
$$\Rightarrow m^2 = (4k)^2$$
$$\Rightarrow m^2 = 16k^2$$
$$\Rightarrow m^2 = 4(4k^2)$$
$$\Rightarrow m^2 = 4j$$ where $$j = 4k^2$$

since j is an integer, your done.
try to do the rest.

13. Feb 8, 2005

### primarygun

Good. When I first notice the cases, I first use mod.
It's simply. After that, I used expansion.
Good method.

14. Feb 8, 2005

### MathStudent

are you reffering to square root or the modulo function?

15. Feb 8, 2005

### primarygun

The method you used + mod

16. Feb 8, 2005

### CollectiveRocker

Thank you guys, I think I've got it. Thanks a bunch.

17. Feb 8, 2005

### MathStudent

Im sorry primary, I don't know what you mean by + mod? do you mind showing me?

18. Feb 8, 2005

### primarygun

19. Feb 8, 2005

### learningphysics

A->B

This is true if A is always false.

Can you prove A is always false.... or in other words can you prove that m^2 cannot be of the form 4k+3? Hint: only two cases m is even or m is odd... in either case it is impossible for m^2 to be of the form 4k+3. If you show this, then you're done.

EDIT: How I approached this problem.

Let m=4k+a, a=1 or 2 or 3

Then m^2=16k^2+8ak+a^2=4(4k^2+2ak)+a^2

So if a=1, m^2=4(....)+1 it's of the form 4k+1
if a=2, m^2=4(....) + 4 it's of the form 4k
if a=3, m^2=4(....) +9 it's of the form 4k+1

So we never get m^2=4k+3.

So the if part "if m^2=4k+3" is always false.

So then I figured, a neater proof of A is false is the best answer to the question.

Last edited: Feb 8, 2005
20. Feb 9, 2005

### mathwonk

ok look. the point is to divide integers into the forms 4[something], 4[something]+1,
4[something]+2, 4[something]+3.

now suppose m = 4[something], say m = 4k. then also m^2 = 16k^2 = 4[4k^2], i.e. m^2 = 4[something] (but for a different something of course.

i.e. the point here is that if m has remainder zero after division by 4, then so does m^2.

now you show that if m has remainder 1 after division by 4, then so does m^2.

and finally if m has remainder 2 after division by 4, then m^2 has remainder zero.

in any case none of these types of numbers m, ever has an m^2 with remainder 3, after division by 4.

so if m^2 does have remainder 3 after division by 4, then also m must have had too.

21. Feb 9, 2005

### learningphysics

Although this is correct, I thought it important to point out that if m has remainder 3 after division by 4 then m^2 has remainder 1.

So there is no integer m such that m^2 has remainder 3 after division by 4.

22. Feb 9, 2005

### mathwonk

by the way math student, I thought the point was not to answer the question to your own satisfaction, but to that of the questioner. that is why teaching is not an exact science.

23. Feb 9, 2005

### MathStudent

What do you mean? What leads you to think I believe teaching is an exact science? I see no evidence of this in this thread. If you read the entire thread from the beginning, you'd see I first tried to guide the OP, only giving hints. From his response it seemed he was lacking some of the fundamental concepts behind the logic, so I attempted to give a more detailed example. He then asked for a very specific example of a proof of one of the cases, which I demonstrated. It was never my intention to just solve the problem for him. Am I missing something? I have read many of your posts, and I value your opinion. Would you mind explaining to me what you think I have done, or not done?

Thanks
-MS

Last edited: Feb 9, 2005
24. Feb 9, 2005

### mathwonk

forgive me as I myself am very apt to be impatient, but that is the quality i seemed to detect from you in this regard. you seem impatient with me as well even now. but i deserve it.

i guess it was your sentence "this has been answered three times already" that inspired my witty comment on the meaning of the term "answered".

my apologies.

best regards

Last edited: Feb 9, 2005
25. Feb 10, 2005