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