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.

Can anyone share a link to proof of this? $${{p-1}\choose{j}}\equiv(-1)^j(\text{mod}\ p)$$ for prime $p$.

share|improve this question

4 Answers 4

up vote 6 down vote accepted

$$\binom {p-1}j=\prod_{1\le r\le j}\frac{p-r}r$$

Now, $\displaystyle p-r\equiv -r\pmod p\implies \frac{p-r}r\equiv-1\pmod p$

share|improve this answer

Since $p$ is prime, $\displaystyle\binom pj\equiv0\pmod p$ for $0\lt j\lt p$.

By Pascal's identity, for $0\lt j\lt p$ we have $$\binom{p-1}j=\binom pj-\binom{p-1}{j-1}\equiv-\binom{p-1}{j-1}\pmod p.$$Since $\displaystyle\binom{p-1}0=1$, it follows by induction that $\displaystyle\binom{p-1}j\equiv(-1)^j\pmod p$

for $0\le j\le p-1$.

share|improve this answer

It is well known that $\binom pi\equiv0\pmod p$ for $0<i<p$. Now Pascal's recurrence gives $\binom{p-1}i\equiv-\binom{p-1}{i-1}\pmod p$ for those$~i$, and so $\binom{p-1}i\equiv(-1)^i\pmod p$ for $0\leq i<p$ follows by an immediate induction on$~i$, with $\binom{p-1}0=1$ as base case.

More generally this gives $\binom{p^k-1}i\equiv(-1)^i\pmod p$ for $0\leq i<p^k$ for any positive integer$~k$ (since $\binom{p^k}i\equiv0\pmod p$ for $0<i<p^k$). This result would be a bit harder to prove by just reducing modulo$~p$ all factors in the expansion of $\binom{p^k}i$ than the basic case (since now some factors in numerator and denominator reduce to$~0$ modulo$~p$).

share|improve this answer

Definition of $a \equiv b \pmod{c}$ requires $a,b,c$ to be integers. (See David Burton's Elementary Number Theory for a definition and a similar problem.) Here is a way to do it. $$(p-1)(p-2)\ldots(p-j) \equiv (-1)^j j! \pmod{p}.$$ Therefore, $$\binom{p-1}{j} j! \equiv (-1)^j j! \pmod{p}.$$ Now we can "cancel" $j!$ because $\gcd(j!, p)=1$ for $1\leq j \leq p-1$ to obtain the result.

share|improve this answer
    
$(p-r)/r$ is interer because we are dividing numbers by modulo $p$. This is the same as multiplying $p-r$ and inverse of $r$ –  Ashot Oct 29 '13 at 9:26
    
No, that may be effectively true, but modulo equivalence is defined for integers, and $(p-r)/r$ may not be an integer. –  anonymous Oct 29 '13 at 9:31
    
@anonymous It is a matter of taste. I would prefer writing "$(p-r)r^{-1}=-1$ in $\mathbf Z/p\mathbf Z$" rather than "$\frac{p-r}r\equiv -1\pmod p$", but they both mean the same. The latter would be ambiguous if an element of the additive group $\mathbf Q/p\mathbf Z$ (it is not a ring) were possibly intended, but that is excluded here. Another matter is that one should not post a critque to another answer as an answer. –  Marc van Leeuwen Oct 29 '13 at 10:04
    
I agree that effectively they are the same, but in an elementary number theory problem, I would not use the fact that $r$ has a inverse, etc. As I have commented in my answer, $\equiv$ is defined on integers, so my answer is just following elementary definitions and basic observations about them. I couldn't care less for a negative vote, but I don't understand it. –  anonymous Oct 29 '13 at 10:12
    
Apologies for the critic. I have deleted that part, while not deleting my solution with a negative vote. –  anonymous Oct 29 '13 at 10:16

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.