The converse and proving whether or not the converse holds

[googlymunja32]

So you are asking, "Is it true that n^p- n is divisible by p for p any prime?"

Yes, it is and for exactly the reason you state: if p is prime then $\left(\begin{array}{c}p \\ i\end{array}\right)$ for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition:
$$\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(p-i)!}$$
as long as i is neither 0 nor p, 0<p-i< p and so neither i! nor (p- i)! have a factor of p. Since p! does, the binomial coefficient is divisible by p. (We need p to be prime so that other factors in i! and (p- i)! do not "combine" to cancel p.)

Now, to show that n^p- n is divisible by p, do exactly what mathman suggested.

First, when n= 1, 1^p- 1= 0 which is divisible by p. Now assume the statement is true for some k: k^p- k= mp for some integer m. Then, by the binomial theorem,
[tex](k+1)^p= \sum_{i=0}^p \left(\begin{array}{c}p \\ i\end{array}\right) k^i[/itex]
subtracting k+1 from that does two things: first it cancels the i=0 term which is 1. Also we can combine the "k" with the i= p term which is k^p so we have k^p- k= mp. The other terms, all with 0< i< p, contain, as above, factors of p.

What would be the converse of this conjecture, How can you prove whether or not the converse holds?

thanks

 

[HallsofIvy]

The converse of "If A then B" is "If B then A" so the converse of "If p is prime then n^p- n is divisible by p (for all n)" is "If n^p- n is divisible by p (for all n) then p is prime". I haven't looked at that in depth but I think you should try "indirect proof": if p is not prime, say p= ij for some integers i and j, can you find find an n so that n^p is not divisible by p?