6
$\begingroup$

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.

2 Answers 2

6

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)$.

  • 0
    I have edit your answer to fix small typo ...2012-01-20
3

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} $

  • 0
    ,Maybe there is some other way of optimization besides AKS method...2012-01-19