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