Proving a Statement with Contraposition: Difficulties and Strategies

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

 

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

 

[CollectiveRocker]

Hold the phone. Now I'm totally confused.

 

[MathStudent]

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

 

[CollectiveRocker]

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

 

[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?)

 

[CollectiveRocker]

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

 

[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?

 

[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

prove these and your done.

 

[CollectiveRocker]

How do you prove case 1?

 

[primarygun]

Using mod or just simply square it.

 

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

 

[primarygun]

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

 

[MathStudent]

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

are you referring to square root or the modulo function?

 

[primarygun]

The method you used + mod

 

[CollectiveRocker]

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

 

[MathStudent]

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

 

[primarygun]

4=0(mod4).
By the way, can you help me?
https://www.physicsforums.com/showthread.php?t=63224

 

[learningphysics]

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.

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.

 

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

 

[learningphysics]

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.

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.

 

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

 

[MathStudent]

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.

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

 

[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

 

[MathStudent]

I wasn't impatient with you, just confused, but I see now that you were referring to my remark in another thread about the numerous postings of this question. I'm afraid I'm not very good with words, and I can see how I came off as annoyed, but please believe I had good intentions. I thought that unifying the threads would benefit both the OP and the people that are here to help, so everyone could collaborate or add their take in the same place. When I added the comment that this question had already been answered, that was a poor choice of words on my part. It was really meant( but admittedly not explicit ) to be a heads up for people to check the other threads first to see what replies had been posted so as to save them the time of writing something that may have already been said.

 

[primarygun]

I'd think the time was optimum to give the solution to the asker as almost all the hints are given.

 

[mathwonk]

It just depends how tired we are of trying to noodge the questioner. Since I just got here on this, I kept thinking "hey I know what to suggest!".

But I admit the only thing I spotted was that the questioner misunderstood the meaning of the phrase "numbers of form 4k+3".

I.e. he was assuming the same k had to be used both times, when he suggested that the only number m such that both m and m^2 were of form 4k+3 was zero or something.

actually back on feb 8, I notice now he logged off with thanks and said he had already got it! so we are talking to the choir only.