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

Math Help - Divisible by 49

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

    Divisible by 49

    Can someone show me the proof by mathematical induction that n^2+n+2 isn't divisible by 49 for every n (natural number).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by OReilly
    Can someone show me the proof by mathematical induction that n^2+n+2 isn't divisible by 49 for every n (natural number).
    You can greatly simplify your problem to reducing it to showing that 7\not |n^2+n+2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    You can greatly simplify your problem to reducing it to showing that 7\not |n^2+n+2
    But it can be divisible by 7. For example for n=3.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by OReilly
    But it can be divisible by 7. For example for n=3.
    I know, but once you exceede 49 it is always true.

    I was just writing out a proof. But I accidently closed my internet thing and lost everything I typed.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    Firstly observe that n^2+n+2 is divisible by 7 if and only if n is congruent to 3 modulo 7: that is, if n is of the form 7x+3. See this by writing it as n^2 - 6n + 9 + 7(n-1), so that it is (n-3)^2 modulo 7.

    Now substitute n=7x+3 into n^2 + n + 2 to get 49x^2 + 49x + 14, which cannot be divisible by 49.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Is this proof valid?

    Supose that for n=k expression is divisible by 49:
    k(k + 1) + 2 = 49a

    Supose that now for n=k+1 expression is also divisible by 49:
    (k + 1)(k + 2) + 2 = 49b


    From first equation we get that k + 1 = \frac{{49a - 2}}{k}.

    Substituting into second equation we get:
    \begin{array}{l}<br />
 (\frac{{49a - 2}}{k})(k + 2) + 2 = 49b \\ <br />
 \frac{{49ak + 98a - 2k - 4}}{k} = 49b - 2 \\ <br />
 49ak + 98a - 2k - 4 = 49bk - 2k \\ <br />
 49ak + 98a - 2k - 4 - 49bk + 2k = 0 \\ <br />
 49ak + 98a - 49bk - 4 = 0 \\ <br />
 \end{array}<br />

    Last expression isn't divisible by 49 so n^2+n+2 isn't divisible by 49.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    You need to show that,
    If,
    n^2+n+2\not = k
    then,
    n^2+n+2\not = k+1

    Equivalently (contropositive),
    If,
    n^2+n+2=k+1
    then,
    n^2+n+2=k

    You shown that:
    if,
    n^2+n+2=k
    then,
    n^2+n+2\not = k+1
    This is not equivalent to the above two statements.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024

    I don't get it...

    I don't understand your proof.

    where am I off?

    If n^2+n+2=k
    then, n^2+n+3=k+1

    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Here is how you do it.
    ---
    You need to show there doth not exist such a 49k such as,
    n^2+n+(2-49k)=0
    Which means there are no integral solution for n.
    If you solve for "n",
    n=\frac{-1\pm \sqrt{1-4(2-49k)}}{2}.
    Note the following, if the expression in the radical is a square then "n" is an integral number because the square root of an odd square is an odd whole number and when added of subtracted to 1 produces an even number and when finally divided by two produces an integral number, thus, if
    1-4(2-49k)=196k-7 is not a square then,
    1-4(2-49(k+1))=1-4(-47-49k)=196k+189 is also not a square.
    Thus, again you need to show that.
    IF,
    196k-7 is not a square
    THEN,
    196k+188 is not a square.
    ~~Contropositive Time~~
    IF,
    196k+188 is a square.
    THEN,
    196k-7 is a square.

    For some reason I cannot continue. I am hoping someone will see this and tell me the next step.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by OReilly
    Is this proof valid?

    Supose that for n=k expression is divisible by 49:
    k(k + 1) + 2 = 49a

    Supose that now for n=k+1 expression is also divisible by 49:
    (k + 1)(k + 2) + 2 = 49b


    From first equation we get that k + 1 = \frac{{49a - 2}}{k}.

    Substituting into second equation we get:
    \begin{array}{l}<br />
 (\frac{{49a - 2}}{k})(k + 2) + 2 = 49b \\ <br />
 \frac{{49ak + 98a - 2k - 4}}{k} = 49b - 2 \\ <br />
 49ak + 98a - 2k - 4 = 49bk - 2k \\ <br />
 49ak + 98a - 2k - 4 - 49bk + 2k = 0 \\ <br />
 49ak + 98a - 49bk - 4 = 0 \\ <br />
 \end{array}<br />

    Last expression isn't divisible by 49 so n^2+n+2 isn't divisible by 49.
    It looks to me that what you have proven is that k^2+k+2 is not divisible
    by 49 for consecutive integral values of k.

    RonL
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Quick
    I don't understand your proof.

    where am I off?

    If n^2+n+2=k
    then, n^2+n+3=k+1

    From his silence on this and departure off on another tangent I think
    ImPerfectHacker agrees with you and he doesn't understand his
    argument either

    It is either so subtle that we can't see the point, or its wrong. I know
    where I'm putting my money (no not in that box under the bed).

    RonL
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Look at post #7. I say it is no good.
    ---
    I still do not see why you chose such a method. The quickest would be quadradic reciprocity.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member Glaysher's Avatar
    Joined
    Aug 2006
    From
    Newton-le-Willows
    Posts
    224
    Quote Originally Posted by ThePerfectHacker
    You need to show that,
    If,
    n^2+n+2\not = k
    then,
    n^2+n+2\not = k+1

    Equivalently (contropositive),
    If,
    n^2+n+2=k+1
    then,
    n^2+n+2=k

    You shown that:
    if,
    n^2+n+2=k
    then,
    n^2+n+2\not = k+1
    This is not equivalent to the above two statements.
    Don't you mean

    Need to prove either

    statement true for n = k implies statement true for n = k + 1

    or

    Contropositive
    Statememt not true for n = k + 1 implies statement not true for n = k

    OReilly showed

    Statement true for n = k implies statement not true for n = k + 1
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by Glaysher
    Don't you mean

    Need to prove either

    statement true for n = k implies statement true for n = k + 1
    wouldn't it imply that n+1=k+1???
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member Glaysher's Avatar
    Joined
    Aug 2006
    From
    Newton-le-Willows
    Posts
    224
    Quote Originally Posted by Quick
    wouldn't it imply that n+1=k+1???
    I assume you are unfamiliar with the principle of mathematical induction

    Usually you are trying to prove something for all natural numbers n

    You show that it is true when n = 1

    Then you assume it is true for some n = k

    It is okay to assume this as we have already proved it for n = 1 so we already know there is at least one possible value for k.

    We then try to prove that it also holds for n = k + 1 assuming that it holds for n= k.

    Once we have done this we have proved it for all natural numbers n as

    True for n = 1 means true for n = 2 means true for n = 3 and so on ...

    This method can be adapted to suit several different purposes
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: February 20th 2013, 10:32 AM
  2. Divisible by 9
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: August 17th 2011, 03:48 AM
  3. Replies: 8
    Last Post: July 3rd 2011, 04:55 PM
  4. Replies: 1
    Last Post: May 8th 2010, 12:49 AM
  5. Replies: 5
    Last Post: January 1st 2010, 02:59 AM

Search Tags


/mathhelpforum @mathhelpforum