# If : $\binom{p-1}{k} \equiv (-1)^k \pmod p$ for all $k$ then $p$ is a prime?

Let $p$ be a prime, and let $1 \leq k \leq p - 1$ be an integer then :

$\binom{p-1}{k} \equiv (-1)^k \pmod p$

Proof :

Because $\binom{p-1}{k}=\frac{(p-1)(p-2)\cdots (p-k)}{k!}$ is an integer and $\gcd(k!,p)=1$

it sufficies to show that :

$(p-1)(p-2)\cdots (p-k) \equiv (-1)^k \cdot k! \pmod p$

which is evident .

Conjecture :

Let $k$ and $p$ be a positive integers such that : $p>4$ and $k\in [1,p-1]$

If : $\binom{p-1}{k} \equiv (-1)^k \pmod p$ for all $k$ then $p$ is a prime number .

I wrote Maple program . The statement is true up to $p=1500$ , and I guess that there is no counterexample at all.

-

In fact, something stronger is true, in that requiring the condition for all the $k$ in $[1,p]$ is overkill: Suppose $\binom{p-1}{k}\equiv (-1)^k\pmod{p}$ for all $1\leq k\leq \lfloor\sqrt{p}\rfloor$. Then for each such $k$, $$\binom{p}{k}=\binom{p-1}{k}+\binom{p-1}{k-1}\equiv (-1)^k+(-1)^{k-1}\equiv 0\pmod{p}.$$ But if $p$ is composite, this fails when $k$ is the smallest prime factor of $p$, which is guaranteed to be between $1$ and $\lfloor\sqrt{p}\rfloor$.

Edit to add proof of the last claim: Let $q$ be the smallest factor of $p$, and write $p=qr$. Then $$\binom{p}{q}=\frac{p!}{q!(p-q)!}=\frac{r(p-1)(p-2)\cdots(p-q+1)}{(q-1)!},$$ the numerator of which is not divisible by $p=qr$ since $q\nmid (p-1)(p-2)\cdots(p-q+1)$.

-
Do you mean $p$ in place of $n$ in the last statement? The $n$ comes out of nowhere... – Steven Stadnicki Jan 18 '12 at 20:03
Yup, great, thanks. – Cam McLeman Jan 18 '12 at 20:28
@CamMcLeman,Can we prove stronger case when $k \in [1,\lfloor \sqrt p \rfloor ]$ ? What do you think ? – pedja Jan 19 '12 at 15:14
Yup. In fact, let me edit the answer directly, since that thought occurred to me while writing it up. – Cam McLeman Jan 19 '12 at 15:20
I have edit your answer to fix small typo ... – pedja Jan 20 '12 at 9:02

HINT $\rm\ \ mod\ p\!:\ {p-1\choose k}\equiv (-1)^k\ \iff\ (1 + x)^p\ \equiv \ 1 + x^p\ \$ since

$$\rm (1+x)^{p-1}\ =\ \sum_{k\ =\ 0}^{p-1}\ {p-1\choose k}\ x^k\ \equiv \ \sum_{k\ =\ 0}^{p-1}\ (-x)^k\ \equiv\ \frac{1-(-x)^p}{1+x}$$

-
the "freshman dream" theorem says :" If $p$ is a prime number then $(x+y)^p \equiv x^p+y^p \pmod p$ ", but not vice versa . – pedja Jan 19 '12 at 10:28
@pedja The primality test $\rm\ n\:$ is prime $\rm\iff (1+x)^n \:\equiv\ 1 + x^n\pmod n\:,\:$ is well-known and easily proved, e.g. see the Wikipedia article on the AKS primality test. Your exercise is an equivalent form of this primality test, stating the polynomial equality in terms of the coefficients. – Bill Dubuque Jan 19 '12 at 15:20
,I see,you are right..I wrote primality test based on this conjecture but it runs in exponential time... – pedja Jan 19 '12 at 15:50
@pedja One way to optimize it to polynomial time is to proceed as in the AKS primality test. – Bill Dubuque Jan 19 '12 at 15:55
,Maybe there is some other way of optimization besides AKS method... – pedja Jan 19 '12 at 16:01