Results 1 to 6 of 6

Math Help - Divisibility by 9

  1. #1
    Junior Member CuriosityCabinet's Avatar
    Joined
    Aug 2010
    From
    UK
    Posts
    32
    Thanks
    1

    Divisibility by 9

    Prove that, for any positive integer n

    n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3} \end{bmatrix}

    is divisible by 9.

    \begin{bmatrix} x \end{bmatrix} denotes the integer part of x.

    I wasn't sure how to go about this question, any help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member CuriosityCabinet's Avatar
    Joined
    Aug 2010
    From
    UK
    Posts
    32
    Thanks
    1
    Please delete. Posted in wrong forum. Sorry :P
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2009
    Posts
    806
    Thanks
    4
    Check whether the given problem is divisible by 9 for n = 4 onwards.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member CuriosityCabinet's Avatar
    Joined
    Aug 2010
    From
    UK
    Posts
    32
    Thanks
    1
    Yes it is. But it comes to 0 for n=1,2,3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by CuriosityCabinet View Post
    Prove that, for any positive integer n

    n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3} \end{bmatrix}

    is divisible by 9.

    \begin{bmatrix} x \end{bmatrix} denotes the integer part of x.

    I wasn't sure how to go about this question, any help?
    Try a case by case verification:

    1.)  n\equiv0\bmod{3}\implies the equation becomes  n(n-1)(n-2) - 2n

    2.)  n\equiv1\bmod{3}\implies the equation becomes  n(n-1)(n-2) - 2(n-1)

    3.)  n\equiv2\bmod{3}\implies the equation becomes  n(n-1)(n-2) - 2(n-2)

    Now simplify each case and use Fermat's little theorem.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by CuriosityCabinet View Post
    Prove that, for any positive integer n

    n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3} \end{bmatrix}

    is divisible by 9.

    \begin{bmatrix} x \end{bmatrix} denotes the integer part of x.

    I wasn't sure how to go about this question, any help?
    Calculate n(n-1)(n-2)=n(n-3n+2)=n^3-3n^2+2n .
    Any integer n can be written in the form \displaystyle{n=3[\frac{n}{3}]+r}, where r=0,1, or 2 . It follows that \displaystyle{3[\frac{n}{3}]=n-r}.

    Now, simplifying, n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3}\end{bmatrix}=n^3-3n^2+2n-2(n-r)=n^3-3n^2+2r .

    Consider three cases:
    1. n\equiv 0 \bmod 3: n^3-3n^2=n^2(n-3) and since n is divisible by 3, n^2 is divisible by 9.

    2. n\equiv 1 \bmod 3 : n^3-3n^2+2=(n-1)(n^2-2n-2)=(n-1)[(n-3)(n+1)+1] , where n-1\equiv 0 \bmod 3 and (n-3)(n+1)+1\equiv -2\cdot 2 +1\equiv 0 \bmod 3. Then (n-1)(n^2-2n-2) is divisible by 9.

    3. n\equiv 2 \bmod 3: n^3-3n^2+4=(n-2)^2(n+1) , and since n-2 \equiv 0 \bmod 3 it follows that (n-2)^2 is divisible by 9.

    For cases 1. and 2. I noticed that 1 and 2 are the roots, respectively, of the polynomials and then used Polynomial Division.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum