Proving a Statement with Contraposition: Difficulties and Strategies

  • Thread starter CollectiveRocker
  • Start date
  • Tags
    Difficulties
In summary, the statement given is if m^2 is of the form 4k+3, then m is of the form 4k+3. The speaker suggests proving this by contraposition and showing that m^2 cannot be of the form 4k+3. They also mention having difficulty with proofs and provide a hint to divide integers into different forms. They proceed to discuss different cases and show that m^2 can never be of the form 4k+3, thus proving the contrapositive statement.
  • #1
CollectiveRocker
137
0
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.
 
Physics news on Phys.org
  • #2
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
Hold the phone. Now I'm totally confused.
 
  • #4
do you agree that the statement I wrote above is the contrapositive?
 
  • #5
Kinda,
why wouldn't it be something like 2k + 3?
 
  • #6
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
I don't even know how to start. How do you recommend proving that?
 
  • #8
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
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.
 
Last edited:
  • #10
How do you prove case 1?
 
  • #11
Using mod or just simply square it.
 
  • #12
[tex] m = 4k [/tex] where k is an integer
[tex]\Rightarrow m^2 = (4k)^2 [/tex]
[tex]\Rightarrow m^2 = 16k^2 [/tex]
[tex]\Rightarrow m^2 = 4(4k^2)[/tex]
[tex]\Rightarrow m^2 = 4j[/tex] where [tex] j = 4k^2[/tex]

since j is an integer, your done.
try to do the rest.
 
  • #13
Good. When I first notice the cases, I first use mod.
It's simply. After that, I used expansion.
Good method.
 
  • #14
primarygun said:
Good. When I first notice the cases, I first use mod.
It's simply. After that, I used expansion.
Good method.
are you reffering to square root or the modulo function?
 
  • #15
The method you used + mod
 
  • #16
Thank you guys, I think I've got it. Thanks a bunch.
 
  • #17
Im sorry primary, I don't know what you mean by + mod? do you mind showing me?
 
  • #19
CollectiveRocker said:
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.
 
Last edited:
  • #20
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
mathwonk said:
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.
 
  • #22
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
mathwonk said:
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
 
Last edited:
  • #24
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:
  • #25
I wasn't impatient with you, just confused, but I see now that you were reffering 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.
 
  • #26
I'd think the time was optimum to give the solution to the asker as almost all the hints are given.
 
  • #27
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.
 

1. What is the concept of contraposition?

Contraposition is a logical concept that states that if a statement is true, then its converse (switching the subject and predicate) is also true. In other words, if "if A then B" is true, then "if not B then not A" is also true.

2. What makes proving a statement with contraposition difficult?

Proving a statement with contraposition can be difficult because it requires a strong understanding of logic and the ability to identify valid logical arguments. It also involves a reverse way of thinking, which can be challenging for some individuals.

3. What are some common strategies for proving a statement with contraposition?

One common strategy is to use a proof by contradiction, where you assume the converse is true and then show that it leads to a contradiction. Another strategy is to use a truth table to show that the original statement and its contrapositive have the same truth values.

4. Can you provide an example of a statement being proved with contraposition?

Sure, let's take the statement "If it is raining, then the ground is wet." This statement can be proved with contraposition by stating its converse, "If the ground is not wet, then it is not raining." We can then use evidence such as the ground being dry to support the truth of the converse and therefore the truth of the original statement.

5. Are there any limitations to proving a statement with contraposition?

One limitation is that not all statements can be proved with contraposition, as it only works for statements in the form of "if A then B." Additionally, it may not be the most efficient or straightforward method for proving a statement in some cases, and other proof techniques may be more suitable.

Similar threads

  • Differential Geometry
Replies
2
Views
1K
  • Science and Math Textbooks
Replies
11
Views
908
Replies
55
Views
1K
  • General Math
Replies
7
Views
1K
  • STEM Academic Advising
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
755
  • Calculus and Beyond Homework Help
Replies
12
Views
5K
Back
Top