How Does Modulo Arithmetic Prove a Combinatorial Identity Involving Primes?

[evinda]

Hey again! (Blush)

If $p \neq 2$ is a prime and $0 \leq k \leq p-1, \text{ prove that: }$
$$\binom{p-1}{k} \equiv (-1)^k \pmod p$$

I thought that I could calculate $\binom{p-1}{k}k!$ :

$$\binom{p-1}{k}k!=\frac{(p-1)!}{k!(p-(k+1))!}k!=\frac{(p-1)!}{(p-(k+1))!}$$

According to Wilson's theorem, $(p-1)! \equiv -1 \pmod p$..
But...what is equal $\mod p$ to $(p-(k+1))!$ ? (Thinking)

 

[evinda]

Hey again! (Blush)

If $p \neq 2$ is a prime and $0 \leq k \leq p-1, \text{ prove that: }$
$$\binom{p-1}{k} \equiv (-1)^k \pmod p$$

I thought that I could calculate $\binom{p-1}{k}k!$ :

$$\binom{p-1}{k}k!=\frac{(p-1)!}{k!(p-(k+1))!}k!=\frac{(p-1)!}{(p-(k+1))!}$$

According to Wilson's theorem, $(p-1)! \equiv -1 \pmod p$..
But...what is equal $\mod p$ to $(p-(k+1))!$ ? (Thinking)

Could I show it maybe like that?

$$ \binom{p-1}{k}=\frac{(p-1)!}{k!(p-(k+1))!}=\frac{(p-k)(p-k+1) \cdots (p-1)}{k!} \equiv \frac{(p-1) \cdots (p-k+1)(p-k)}{k!} \equiv \frac{(-1) \cdots (-k+1)(-k)}{k!} \equiv \frac{(-1)^k k!}{k!} \equiv (-1)^k \pmod p $$ ?
(Nerd)

 

[I like Serena]

Could I show it maybe like that?

$$ \binom{p-1}{k}=\frac{(p-1)!}{k!(p-(k+1))!}=\frac{(p-k)(p-k+1) \cdots (p-1)}{k!} \equiv \frac{(p-1) \cdots (p-k+1)(p-k)}{k!} \equiv \frac{(-1) \cdots (-k+1)(-k)}{k!} \equiv \frac{(-1)^k k!}{k!} \equiv (-1)^k \pmod p $$ ?
(Nerd)

Looks good! (Nod)

 

[evinda]

Looks good! (Nod)

Nice,thank you very much! (Happy)

 

[CellCoree]

Hi there! Great job on starting your proof! To find what $(p-(k+1))!$ is congruent to modulo $p$, we can use the fact that $p$ is a prime number. This means that every number from $1$ to $p-1$ has an inverse modulo $p$. In other words, for each number $a$ in this range, there exists a number $a'$ such that $a \cdot a' \equiv 1 \pmod p$.

Now, since $k$ is between $0$ and $p-1$, $p-(k+1)$ must be between $-1$ and $p-2$. But since $p$ is an odd prime, $p-2$ is even and thus has an inverse modulo $p$. This means that $p-(k+1)$ has an inverse modulo $p$ as well. Let's call this inverse $b$.

Now, we can rewrite $(p-(k+1))!$ as:
$$(p-(k+1))! \equiv (p-1)! \cdot b \cdot (b-1) \cdot (b-2) \cdot ... \cdot (b-(k-1)) \pmod p$$

Since $(p-1)! \equiv -1 \pmod p$, we can substitute this into our equation:
$$(p-(k+1))! \equiv -1 \cdot b \cdot (b-1) \cdot (b-2) \cdot ... \cdot (b-(k-1)) \pmod p$$

But since $b$ is the inverse of $p-(k+1)$ modulo $p$, we know that $p-(k+1) \cdot b \equiv 1 \pmod p$. This means that we can further simplify our equation to:
$$(p-(k+1))! \equiv -(b-1) \cdot (b-2) \cdot ... \cdot (b-(k-1)) \pmod p$$

Now, remember that $b$ is the inverse of $p-(k+1)$ modulo $p$, so $b \equiv \frac{1}{p-(k+1)} \pmod p$. This means that $b-1 \equiv \frac{1}{p-(k+1)}-1 \equiv \frac{