1. Not finding help here? Sign up for a free 30min 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!

Odd positive integer proof

  1. Nov 20, 2005 #1
    Can't figure it out

    Prove that if n is an odd positive integer, then one of the numbers n+5 or n+7 is divisible by 4

    My thoughts I dunno if this is right- Multiply n+5 and n+7, because if one of them is a multiple by 4 then shouldn't their product be divisible 4
     
  2. jcsd
  3. Nov 20, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    2 times 2 is divisible by 4, neither of 2 or 2 is divisible by 4.


    whenever you hear the phrase: suppose n is odd, then let n=2m+1 will probably help. It does here, though it is then a two line proof. you can do it in one line if you just think mod 4 from the start.
     
    Last edited: Nov 20, 2005
  4. Nov 20, 2005 #3

    turbo

    User Avatar
    Gold Member

    Add a series of positive odd integers to 5 and to 7 and jot down the results. Just add as if n=1,3,5,7 etc. You shouldn't get too far down the list before you notice a pattern, and can construct your proof.
     
  5. Nov 20, 2005 #4
    Hi!

    The problem can be easily solved using congruencies modulus 4. I will use the symbol '=' to denote 'congruent with'

    First, n is and odd positive integer then n=1 (mod 2) and then one of the following holds

    a) n=1 (mod 4)
    b) n=3 (mod 4)

    now we have that

    5=1 (mod 4)
    and 7=3 (mod 4)


    if case a) holds then

    (n+5)= 2 (mod 4)
    (n+7)= 0 (mod 4)

    if case b) holds then

    (n+5)= 0 (mod 4)
    (n+7)= 2 (mod 4)

    Since a) and b) cannot be satisfied simulstaneously then just one of the numbers n+5 or n+7 is divisible by 4.

    Note: what i mean with "congruencies", (mod 4) and the equations above?, This:


    1=1 (mod 4), 2=2 (mod 4), 3=3 (mod 4), 4=0 (mod 4),
    5=1 (mod 4), 6=2 (mod 4), ............. 8=0 (mod 4) and so on....


    To the left of the '=' signs is the number in question, and to right the residue when it is divided by 4.
     
  6. Nov 20, 2005 #5
    oh ok, thanks for your help

    What's mod???
     
  7. Nov 20, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    we're supposed to not just give people the answers, mathsphys. your 14 line answer was in fact my one line answer.
     
  8. Nov 20, 2005 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    remainder after division.

    x= y mod n means x and y leave the same remainder upon division by n.


    obviously any odd number must leave remainder 1 or 3 after division by 4. remainder 0 or 2 means that it is either a multiple of 4 or 2 more than a multiple of 4 and they're both even numbers (remember the definitions: something is even if it is 2k and odd if it is 2k+1)
     
  9. Nov 20, 2005 #8
    I get it now, thanks alot man
     
  10. Nov 20, 2005 #9
    Sorry!

    uh, i didn't know sorry matt, i was just trying to help. In fact i do not read your answer, just jmn problem. it will not happend again, just clues from now ;).

    Hi Jmn, i think that if you are going to be solving problems of this kind (arithmetical ones) it would be nice if you can check the notion of modules and congruencies, and some theorems/properties related to them, they will save you a lot of time.

    http://mathworld.wolfram.com/Modulus.html this link explains what is a modulus.

    and this one explains congruencies
    http://mathworld.wolfram.com/Congruence.html

    Regards

    P.S. By the way, i can write my "14 lines answer" in a line also, wait, in half a line.. ;) ..even..
     
    Last edited: Nov 20, 2005
  11. Nov 20, 2005 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    *modulo* or just plain *mod* arithmetic. modules are something else entirely and completely unrelated to the question (well, almost completely unrelated).
     
  12. Nov 20, 2005 #11
    yep

    yep, modulus, my typos ;)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?