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!

Prove that 11^2 does not devide n^2+3n+5

  1. Jun 13, 2009 #1
    1. The problem statement, all variables and given/known data

    prove that 11^2 does not devide n^2+3n+5; for any n.

    In order for this to make sense n must be an integer.

    2. Relevant equations



    3. The attempt at a solution

    want to show that n^2+3n+5 is not congruent to 0(mod 121)

    Assume towards a contradiction that 11^2 divides n^2+3n+5

    we can rewrite n^2+3n+5=(n+7)(n-4)+33.

    since i assumed that 11^2|n^2+3n+5 then 11^2|(n+7)(n-4)+33

    (now is the part that i am not sure about)

    but 11^2 does not divide 33. Therefore 11^2 does not divide n^2+3n+5.

    I am not sure about this last step in the argument.

    thanks for any help.
     
  2. jcsd
  3. Jun 13, 2009 #2
    I don't think you need any clever factorizations to do this problem. The simplest factorization possible will give you a lot of insight. Assuming that my reasoning was correct, working in mod 3 is a good way to approach this type of problem (in fact, when dealing with squares, working in mod 3 or 9 is helpful; for instance, squares are congruent to either 0 or 1 in mod 3).

    *EDIT* Actually, I think I made a mistake somewhere. Your argument can work but I think you are missing a step.
     
    Last edited: Jun 13, 2009
  4. Jun 13, 2009 #3
    Considering the whole thing mod 121 quickly gets messy, and we see that 11|33 so we should instead try to see what we get if we consider it modulo 11 instead. From your factorization you should be able to see that,
    11|(n+7)(n-4)+33
    What can you say about n modulo 11 from this?
     
  5. Jun 13, 2009 #4
    Ah thanks gunch. rbetan, you last implication is not justified, but gunch has provided the missing step.
     
  6. Jun 14, 2009 #5
    hey gunch: I do not see how does it follow that 11|(n+7)(n-4)+33; can any one explain this step.

    Now taking for granted that 11|(n+7)(n-4)+33. then (n+7)(n-4)+33= 0(mod 11)

    so (n+7)(n-4)=-33(mod11); but -33(mod11)=0; so (n+7)(n-4)=0(mod11)

    so it follows that 11|(n+7)(n-7) then 11^2|(n+7)(n-7)

    but 11^2 does not divide 33. Therefore, 11^2 cannot divide (n+7)(n-4)+33.

    so 11^2 does not divide n^2+3n+5.

    is this correct.
     
  7. Jun 14, 2009 #6
    It doesn't follow, but it patches your original argument. The whole point is that we know 11 divides 33 but if 11 doesn't even divide (n+7)(n-4), then there is nothing left to prove because clearly 11^2 won't divide (n+7)(n-4) if 11 does not. Thus, we assume that 11 does divide (n+7)(n-4). Noting that n + 7 = n - 4 (mod 11), we know that 11^2 divides (n+7)(n-4) if 11 does, but now 11^2 does not divide 33, so 11^2 cannot divide (n+7)(n-4) + 33.
     
  8. Jun 15, 2009 #7
    Using the quadratic formula and quadratic reciprocity you can show that 11^2 indeed divides (n+7)(n-4). Therefore, it divides (n+7)(n-4) but not 33. Hence it's not divisible by 11^2
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook