# Does $(x+1)^p \not \equiv_p x^p + 1$ for some $x$ hold if $p$ isn't prime?

A previous post revealed an error in the textbook. Now I'm beginning to doubt another closely related claim:

$$(x+1)^p \equiv_p x^p + 1$$ for all $$x \in \mathbb{Z}$$ if and only if $$p$$ is prime.

I'm pretty confident in the argument in one direction. Using the Binomial Theorem we write $$(x+1)^p$$ as $$\sum_{k=0}^p \binom{p}{k} x^k$$ Then any coefficient other than the first and last is of the form $$p \frac{(p-1)!}{(p-k)!\,k!}\,.$$ Because the whole coefficient is an integer the fraction must either also be an integer or a multiple of $$1/p$$. The latter can't be since, as long as we're not dealing with an edge case, neither factorial on the bottom contains a $$p$$. Thus, the fraction must be an integer. And that leaves us with only the terms $$x^p$$ and $$1$$ as we'd hoped for.

In the other direction one can show following similar lines of reasoning that if $$p$$ isn't prime at least one intermediate coefficient isn't a multiple of $$p$$. However, as Ethan MacBrough pointed out in a similar case here that's not enough to conclude the argument. It may be that by some conspiracy the intermediate terms still cancel for all $$x$$.

That raises the question: did the textbook at least get this one right?

• Is the statement assumed true for all $x$ is $p$ is prime? – Mostafa Ayaz Mar 20 at 23:30
• Yes. At least that's what's being asked to show. – Sebastian Oberhoff Mar 20 at 23:32

## 1 Answer

This statement is also false. A number for which this is true is called a Carmichael number. Non-prime Carmichael numbers are somewhat rare, but they exist. The smallest is 561.

To see the equivalence between the stated property and that of being a Carmichael number, suppose $$n$$ is a Carmichael number, so by definition we know for all $$x$$ we have $$x^n\equiv x$$. Thus in particular $$(x+1)^n\equiv_n x+1\equiv_n x^n+1$$.

Conversely, if $$n$$ satisfies the stated property then we can show that $$n$$ is a Carmichael number by induction. Suppose we've proven that $$(x-1)^n\equiv_n = x-1$$. By the assumed property, we have $$x^n=((x-1)+1)^n\equiv_n (x-1)^n+1$$, and by the induction hypothesis this is equivalent modulo $$n$$ to $$x-1+1=x$$. The base case where $$x=0$$ is trivial.

• I'm not very experienced with this stuff. Can you help me see why the property used to define Carmichael numbers given there implies that this equivalence holds for them? – Sebastian Oberhoff Mar 20 at 23:57
• @SebastianOberhoff added clarifications. – Ethan MacBrough Mar 21 at 0:07
• Thank you very much. I guess the authors should consider themselves fortunate that number theory isn't their declared field of specialty. – Sebastian Oberhoff Mar 21 at 0:15