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

1. ## 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

2. Originally Posted by Qwertyuiop23
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.

3. 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?