# ${{p-1}\choose{j}}\equiv(-1)^j \pmod p$ for prime $p$

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

-

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

-

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

-

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

-

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.

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