Results 1 to 3 of 3

Math Help - Prove that (n^x)-n is divisible by x but only if x is prime

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    11

    Prove that (n^x)-n is divisible by x but only if x is prime

    Prove that (n^x)-n is divisible by x but only if x is prime

    How can I prove the above conjecture is true using induction and the
    Binomial theorem?

    I know about proving for n=k (i.e n=1) then assume true for n=(k+1)
    therefore when ever k is true then (k+1) is true and I have proved it for
    several values of x (all primes).

    I know that P(k+1)-P(k) when x is a prime the xth line of Pascal's
    Triangle the coefficients of k are those numbers in that line.
    Then I know binomial expression puts a coefficient in front of each term.
    And this is as far as I have gotten. I did try proving n!/(r!(n-r)!) is
    divisible by x when x is a prime but I couldn't get it.

    I know it can be done as our teacher set it while he was away but when
    searching around someone told me this "This is false. The numbers that
    make this false are called Carmichael numbers. For example, take x=561."
    Obviously I don't believe them but still it confused me.

    The most confusing part is trying to prove if x is a prime. How could I
    find if it is divisible by x when x is a prime, how to define a prime
    number?

    I'll show proof the P(n) = (n^x)-n when x=2 is divisible by 2
    Prove for a simple value P(1) = (1^2)-1 = 0 so true for P(1)
    Assume true for P(k) then prove for P(k+1)
    P(k) = k(k-1)=2A (factorizing k^2-n, where A is a positive integer)
    P(k+1) = (k+1)(k+1-1)
    k(k+1)
    k^2+k
    k^2+k-k+k
    k^2+2k-k
    k^2-k+2k
    k(k-1)+2k
    2A+2k (substitute in k(k-1) = 2A)
    2(A+k)
    Therefor true for P(k) and P(k+1) is true whenever P(k) is true so true
    for all P(n) = n^2-n for all positive integers of n. (principle of
    induction)

    Cheers
    Lance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Qwertyuiop23 View Post
    Prove that (n^x)-n is divisible by x but only if x is prime

    [snip]
    Lance
    2^561 - 2 is divisible by 561
    37^561 - 37 is divisible by 561

    561 is not prime -- it is a carmichael number.

    Try any carmichael number.
    The statement is false.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    11
    I made the conjecture about divisible by x when it is a prime so I must have been wrong.

    If I was given P(n) = (n^x)-n and was told to write a conjecture for when P(n) was divisible by x for all n and was told it had something to do with Pascals Triangle what conjecture should I have made?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: February 3rd 2011, 06:49 PM
  3. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  4. divisible by prime
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 16th 2010, 06:34 PM
  5. prove that then n is divisible by 11
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2008, 11:05 PM

Search Tags


/mathhelpforum @mathhelpforum