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!

Can someone look at my proof?

  1. Mar 2, 2012 #1
    Prove: For all integer n, 4 does NOT divide n2 + 5

    The definition of | means the definition of divide.

    348sso9.jpg

    I need very thorough correction, down to the last support for every thing. Thank you
     
  2. jcsd
  3. Mar 3, 2012 #2

    Mark44

    Staff: Mentor

    You're doing more work than you need to.
    For case 1, when n = 2k, you have n2 + 5 = (2k)2 + 5 = 4k2 + 5 = 4(k2 + 1) + 1. Clearly 4 | 4(k2 + 1), but it can't also divide 4(k2 + 1) + 1.

    For case 2, use a similar argument.
     
  4. Mar 3, 2012 #3

    Bacle2

    User Avatar
    Science Advisor

    I would state, re the first that from:

    4k2+5=4t ,

    you may also write:

    5=4(t-k2) , for t,k2 integers, which is not possible, i.e.,

    5=4x has no solutions in integers (e.g. 4 is not invertible in integers.).

    But that is a matter of preference (since I don't know the constraints; what you are or not allowed to work with).

    To check possible congruences (mod4) , check the values (mod4) of each of the squares of : 4k, 4k+1,4k+2, 4k+3.

    ------------------------------

    OR:

    4|(n2+5) , then n2+5==0(mod4)→

    n2==3mod4. But you can check that n2==0,1,2 but not 3 (mod4).
     
    Last edited: Mar 3, 2012
  5. Mar 3, 2012 #4
    But there is nothing wrong with my proof right?
     
  6. Mar 3, 2012 #5

    Deveno

    User Avatar
    Science Advisor

    rather than use "not an integer" arguments, it would be cleaner to stay totally within the integers.

    that is, if 4k2+ 5 = 4t

    then 5 = 4(t - k2) → 4|5, impossible.

    similarly, if 4k2 + 4k + 9 = 4t

    then 9 = 4(t - k2 + k) → 4|9, also impossible.

    *******

    alternate proof # 1:

    if 4|n2 + 5, then n2+5 must be even, so n2 must be odd → n is odd.

    therefore n = 4k+1 or 4k+3 (all odd numbers are of one of these 2 forms).

    (4k+1)2 + 5 = 16k2 + 8k + 6,

    if this is divisible by 4, then 16k2 + 8k + 6 = 4t, so

    6 = 4(t - 4k2 - 2k) → 4|6.

    (4k+3)2 + 5 = 16k2 + 24k + 14, and as before:

    16k2 + 24k + 14 = 4t implies 14 = 4(t - 4k2 - 6k),

    so that 4|14, a contradiction.

    *******

    alternate proof #2:

    let [a] = the residue class of a mod 4.

    if 4|n2 + 5, then [n2 + 5] = [0], so [n2] = [-5] = [3].

    but [n2] = [n][n] = [0][0], [1][1],[2][2], or [3][3].

    [0][0] = [0] ≠ [3]
    [1][1] = [1] ≠ [3]
    [2][2] = [4] = [0] ≠ [3]
    [3][3] = [9] = [1] ≠ [3],

    so there is no n for which [n2] = [3], and so no n for which [n2+5] = [0], so 4 does not divide n2+ 5

    ********

    why provide 3 proofs, when all you want to know is: is yours OK? hmm...it's a mystery, no? perhaps you think about it for a little bit.
     
    Last edited: Mar 3, 2012
  7. Mar 3, 2012 #6
    I like the way you did the first two proofs, they look simple and to the point. I understand that there are many ways to do the same proof and it is always better to be able to write proofs efficiently because not all proofs are always this short.

    I am reluctant to use your mod proof because we have not learned it that way. I have an exam coming up and I want to be able to just follow the professors style to get full points :tongue:
     
  8. Mar 3, 2012 #7

    Deveno

    User Avatar
    Science Advisor

    that is a fair point.. professors usually appreciate it when students don't "get ahead of themselves" and use theorems/concepts that haven't been covered yet.

    that said, there's no harm in "looking ahead" and understanding that what you have done can be viewed an alternate way. it's like looking at two views of a 3-D object: one from the front, and one from the side. neither view is "wrong", but they are certainly different.
     
  9. Mar 3, 2012 #8

    Bacle2

    User Avatar
    Science Advisor

    Proof seems correct; only thing is I don't know what you

    are allowed to use (mostly: can you bring up rationals, or do you have to stay within

    the integers?). If everything your using is allowed, it seems correct to me.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook