Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Math Help - Divisibility by 121

  1. #1
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340

    Divisibility by 121

    Can someone help me to prove that n^2+3n+5 is not divisible by 121 for any n \in Z ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by OReilly
    Can someone help me to prove that n^2+3n+5 is not divisible by 121 for any n \in Z ?
    Suppose that for some n \in \mathbb{Z} that n^2+3n+5 is divisible by 121
    then the exists a \kappa such that:

    <br />
n^2+3n+5=121\ \kappa<br />

    So from the quadratic formula we have:

    <br />
n=\frac{-3 \pm \sqrt{9-4(5-121\ \kappa})}{2}<br />

    Which implies that  \sqrt{9-4(5-121\ \kappa}) is an odd integer, m say. So:

    <br />
121\times4\times \kappa - 11=m^2<br />

    but the LHS is divisible by 11, and as m^2 is a square it is also divisible
    by 121 (which is 11^2), but that would imply that 11 is divisible by 121; a
    contradiction, so no such n exits.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Can you just explain me this part, I didn't quite understand it.

    Quote Originally Posted by CaptainBlack

    <br />
121\times4\times \kappa - 11=m^2<br />

    but the LHS is divisible by 11, and as m^2 is a square it is also divisible
    by 121 (which is 11^2), but that would imply that 11 is divisible by 121; a
    contradiction, so no such n exits.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    Can someone help me to prove that n^2+3n+5 is not divisible by 121 for any n \in Z ?
    If X = n^2+3n+5 is divisible by 121 then so is 4X = 4n^2+12n+20 = (2n+3)^2 + 11. If 4X is divisible by 121 then it's divisible by 11 and hence 11 divides (2n+3)^2. If 11 divides a perfect square (2n+3)^2 then it divides 2n+3: and that implies that 121 divides (2n+3)^2. So we have 121 dividing (2n+3)^2 and (2n+3)^2+11, hence the difference, which is 11. But that's a contradiction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Can you just explain me this part, I didn't quite understand it.

    Quote Originally Posted by CaptainBlack

    <br />
121\times4\times \kappa - 11=m^2<br />

    but the LHS is divisible by 11, and as m^2 is a square it is also divisible
    by 121 (which is 11^2), but that would imply that 11 is divisible by 121; a
    contradiction, so no such n exits.

    RonL
    If a square is divisible by a prime, it is also divisible by the square of the
    prime. It's a consequence of the fundamental theorem of arithmetic, that
    the decomposition of a number into a product of primes is essential unique.

    So the left hand side of the equation being divisible by 11 implies that the
    right hand side is also divisible by 11, but the right hand side is a square.
    So the right hand side is divisible by 121 (the square of 11). This implies
    that the left hand side is divisible by 121, and so that 11 is divisible by
    121 which is a contradiction.

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    When I was trying to solve the problem I have done this:
    \begin{array}{l}<br />
 n^2  + 3n + 5 = 121k \\ <br />
 n^2  - 8n + 11n + 16 - 11 = 121k \\ <br />
 (n - 4)^2  + 11n - 11 = 121k \\ <br />
 (n - 4)^2  = 121k - 11n + 11 \\ <br />
 (n - 4)^2  = 11(11k - n + 1) \\ <br />
 \end{array}<br />

    But I have stoped there.

    Let me see if I have understood good.
    11(11k - n + 1) is obviosly divisible by 11, so (n - 4)^2 is also divisible by 11. But (n - 4)^2 is also divisible by 11^2 which now implies that 11(11k - n + 1) is divisible by 121. So we get that \frac{{11}}{{121}} = \frac{{11k - n + 1}}{{(n - 4)^2 }} which shows that 11 is not divisible by 121.

    Is that correct?

    I didn't know that if a square is divisible by a prime, it is also divisible by the square of the prime. Boy, I feel stupid and embarrassed now!

    Divisibility of numbers is simply killing me, I just can't solve any harder problem. I am not expert, but I think that in order to solve those problems you need to know Number theory. Since I am on level of Algebra 1 and 2 for high school (problem that I have posted is from Algebra 1) I find that many harder problems constructed for learning Algebra 1 and 2 that concerns divisibility are based on writers thorought knowledge of Number theory. I don't know if I am wrong, but that's my impression. Either that, or I must find excuse!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by OReilly
    I didn't know that if a square is divisible by a prime, it is also divisible by the square of the prime.
    Proof,
    Let p|ab then, p|a or p\not | a. If p\not |a then, \gcd(a,p)=1 then, p|b by Euclid's Lemma. Thus, p|a \mbox{ or }p|b.
    Thus, given p|a^2 you have, p|aa thus, p|a or p|a thus, p|a definetly. Now, if c|d then, c^n|d^n but since p|a then p^2|a^2 if you want to be formal about it

    Quote Originally Posted by OReilly
    Boy, I feel stupid and embarrassed now!
    That is right keep on feeling stupid.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    When I was trying to solve the problem I have done this:
    \begin{array}{l}<br />
 n^2  + 3n + 5 = 121k \\ <br />
 n^2  - 8n + 11n + 16 - 11 = 121k \\ <br />
 (n - 4)^2  + 11n - 11 = 121k \\ <br />
 (n - 4)^2  = 121k - 11n + 11 \\ <br />
 (n - 4)^2  = 11(11k - n + 1) \\ <br />
 \end{array}<br />

    But I have stoped there.

    Let me see if I have understood good.
    11(11k - n + 1) is obviosly divisible by 11, so (n - 4)^2 is also divisible by 11. But (n - 4)^2 is also divisible by 11^2 which now implies that 11(11k - n + 1) is divisible by 121. So we get that \frac{{11}}{{121}} = \frac{{11k - n + 1}}{{(n - 4)^2 }}
    I don't see how this last equation follows from what you say it does.


    which shows that 11 is not divisible by 121.

    Is that correct?

    I didn't know that if a square is divisible by a prime, it is also divisible by the square of the prime. Boy, I feel stupid and embarrassed now!
    RonL
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by CaptainBlack
    I don't see how this last equation follows from what you say it does.
    RonL
    My lack of understanding again!

    Let me try again.

    From my example we have:
    \begin{array}{l}<br />
 (n - 4)^2  - 11 = 121k - 11n \\ <br />
 (n - 4)^2  - 11 = 11(11k - n) \\ <br />
 \end{array}<br />

    That implies that (n - 4)^2  - 11 is divisible by 11. But (n - 4)^2 is also divisible by 121 but we would have that (n - 4)^2  - 11 is also divisble by 121, which is different.

    Is that ok?
    Last edited by OReilly; May 21st 2006 at 04:41 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Not necessarily, you proof falls:
    But (n-4)^2 is also divisible by 121 but we would have that (n-4)^2-11.is also divisble by 121
    Note if (n-4)^2=121 then, (n-4)^2-11=110 which is not divisible by 121. Thus, that statement is false.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    Not necessarily, you proof falls:


    Note if (n-4)^2=121 then, (n-4)^2-11=110 which is not divisible by 121. Thus, that statement is false.
    That was what I have said. I said "which is different" after "is also divisble by 121". I should have said "which is contradictory".
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    If,
    a|b,a\not |c then, a\not |(b+c)

    According to you,
    a|b,a\not |c then, a|(b+c)

    Where,
    a=121
    b=(n-4)^2
    c=11

    Again in Line,
    But (n-4)^2 is also divisible by 121 but we would have that (n-4)^2-11.is also divisble by 121
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    If,
    a|b,a\not |c then, a\not |(b+c)

    According to you,
    a|b,a\not |c then, a|(b+c)

    Where,
    a=121
    b=(n-4)^2
    c=11

    Again in Line,
    No, I said exactly what you have said. That is NOT divisible not that is divisible. Maybe I didn't wrote it good.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    From the equation,
    <br />
\begin{array}{l} (n - 4)^2 - 11 = 121k - 11n \\ (n - 4)^2 - 11 = 11(11k - n) \\ \end{array}<br />
    Your proof.

    1)RHS is divisible by 11,
    2)So LHS is divisible by 11,
    3) 11|((n-4)^2-11)
    4)Since, 11|(-11) so, 11|(n-4)^2
    5)So, 121 divides (n-4)^2
    6)But then, 121 divides 11.
    7)Contradiction.

    Explain to me step 6!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    From the equation,
    <br />
\begin{array}{l} (n - 4)^2 - 11 = 121k - 11n \\ (n - 4)^2 - 11 = 11(11k - n) \\ \end{array}<br />
    Your proof.

    1)RHS is divisible by 11,
    2)So LHS is divisible by 11,
    3) 11|((n-4)^2-11)
    4)Since, 11|(-11) so, 11|(n-4)^2
    5)So, 121 divides (n-4)^2
    6)But then, 121 divides 11.
    7)Contradiction.

    Explain to me step 6!
    121 doesn't divide 11, obviously.
    I don't know what I have to explain?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum