Results 1 to 4 of 4

Math Help - Divisibility

  1. #1
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    Divisibility

    I need to prove this by induction.

    Let n be in Z. prove that 3 divides n^3 - n

    This is what I have:

    Let n=1, 3 divides 0 so the base case holds

    assuming k=n so 3 divides k^3-k

    so it is left to show that 3 divides (K+1)^3 -(K+1)

    .......
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by JCIR View Post
    I need to prove this by induction.

    Let n be in Z. prove that 3 divides n^3 - n

    This is what I have:

    Let n=1, 3 divides 0 so the base case holds

    assuming k=n so 3 divides k^3-k

    so it is left to show that 3 divides (K+1)^3 -(K+1)

    .......
    Expanding the cube we get

    k^3+3k^2+3k+1-k-1=k^3-k+3k^2+3k=(k^3-k)+3(k^2+k)

    3 divides the first term by the induction hypothsis and 3 divides the 2nd term because it is a multiple of 3.

    So we are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68
    Thanks alot I just need that last step.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Here's a generalisation

    Given a prime p for every natural number n we have: n^p\equiv{n}(\bmod.p) (Fermat's little Theorem)

    Let us show it by induction as well.

    The assertion is obvious for n=0

    Now suppose it holds for n (1), we'll show it's also true for n+1

    By the Binomial Theorem: (n+1)^p=\sum_{k=0}^{p}\binom{p}{k}\cdot{n^k}

    But now note that: \binom{p}{k}\equiv{0}(\bmod.p) whenever 1 \leq k\leq{p-1} (k natural) indeed \binom{p}{k}=p\cdot{\frac{(p-1)...(p-k+1)}{k!}} is a natural number, but since 1 \leq k\leq{p-1} then k! doesn't divide p so it must be that \binom{p}{k}\equiv{0}(\bmod.p)

    Thus we have: (n+1)^p=\sum_{k=0}^{p}\binom{p}{k}\cdot{n^k}\equiv  {n^p+1}(\bmod.p)

    And by (1) we have: n^p\equiv{n}(\bmod.p) so that (n+1)^p\equiv{n+1}(\bmod.p)
    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, 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