Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
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
1  
@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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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