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