1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove This!

  1. Feb 8, 2005 #1
    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. jcsd
  3. Feb 8, 2005 #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.
     
  4. Feb 8, 2005 #3
    Hold the phone. Now I'm totally confused.
     
  5. Feb 8, 2005 #4
    do you agree that the statement I wrote above is the contrapositive?
     
  6. Feb 8, 2005 #5
    Kinda,
    why wouldn't it be something like 2k + 3?
     
  7. Feb 8, 2005 #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?)
     
  8. Feb 8, 2005 #7
    I don't even know how to start. How do you recommend proving that?
     
  9. Feb 8, 2005 #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?
     
  10. Feb 8, 2005 #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: Feb 9, 2005
  11. Feb 8, 2005 #10
    How do you prove case 1?
     
  12. Feb 8, 2005 #11
    Using mod or just simply square it.
     
  13. Feb 8, 2005 #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.
     
  14. Feb 8, 2005 #13
    Good. When I first notice the cases, I first use mod.
    It's simply. After that, I used expansion.
    Good method.
     
  15. Feb 8, 2005 #14
    are you reffering to square root or the modulo function?
     
  16. Feb 8, 2005 #15
    The method you used + mod
     
  17. Feb 8, 2005 #16
    Thank you guys, I think I've got it. Thanks a bunch.
     
  18. Feb 8, 2005 #17
    Im sorry primary, I don't know what you mean by + mod? do you mind showing me?
     
  19. Feb 8, 2005 #18
  20. Feb 8, 2005 #19

    learningphysics

    User Avatar
    Homework Helper

    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
  21. Feb 9, 2005 #20

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  22. Feb 9, 2005 #21

    learningphysics

    User Avatar
    Homework Helper

    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.
     
  23. Feb 9, 2005 #22

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  24. Feb 9, 2005 #23
    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
  25. Feb 9, 2005 #24

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    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
  26. Feb 10, 2005 #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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook