1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sebastian Oberhoff Mar 20 at 23:57
  • $\begingroup$ @SebastianOberhoff added clarifications. $\endgroup$ – Ethan MacBrough Mar 21 at 0:07
  • $\begingroup$ Thank you very much. I guess the authors should consider themselves fortunate that number theory isn't their declared field of specialty. $\endgroup$ – Sebastian Oberhoff Mar 21 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.