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

  • 1
    Do you mean $p$ in place of $n$ in the last statement? The $n$ comes out of nowhere...2012-01-18
  • 0
    Yup, great, thanks.2012-01-18
  • 1
    @CamMcLeman,Can we prove stronger case when $k \in [1,\lfloor \sqrt p \rfloor ]$ ? What do you think ?2012-01-19
  • 0
    Yup. In fact, let me edit the answer directly, since that thought occurred to me while writing it up.2012-01-19
  • 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
    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 .2012-01-19
  • 0
    @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](http://en.wikipedia.org/wiki/AKS_primality_test) on the AKS primality test. Your exercise is an equivalent form of this primality test, stating the polynomial equality in terms of the coefficients.2012-01-19
  • 0
    ,I see,you are right..I wrote primality test based on this conjecture but it runs in exponential time...2012-01-19
  • 0
    @pedja One way to optimize it to polynomial time is to proceed as in the AKS primality test.2012-01-19
  • 0
    ,Maybe there is some other way of optimization besides AKS method...2012-01-19