Prove $k \equiv (-1)^n \bmod p$

Question

Let $n$ be a positive integer.

Let $p$ be a prime number.

Define

$k = \frac{(np)!}{n!p^n}$

Prove $k$ is a positive integer and $k$ $\equiv$ $(-1)^n\bmod p$.

Answer 1

Define $$k(n) = \frac{(np)!}{n!p^n}$$ Then $$\frac{k(m+1)}{k(m)}=\frac{((m+1)p)!}{(m+1)!p^{m+1}}\frac{m!p^m}{(mp)!}$$ $$=(mp+1)(mp+2)...(mp+p-1) \text{, an integer.}$$ $$\equiv (p-1)!\equiv -1\bmod p \text{, by Wilson's Theorem.}$$

$k(1)=(p-1)!\equiv -1\bmod p$ and therefore $k(n)$ is an integer and $k(n)\equiv (-1)^n\bmod p$.

Answer 2

Outline of this exercise (which I made mostly for myself, I found this a fun problem!)

1. $(np)!$ can be written as $$1 \cdot \ldots \cdot p \cdot (p+1) \cdot \ldots \cdot (2p) \cdot (2p+1) \cdot \ldots \cdot ((n-1)p) \cdot ((n-1)p +1) \cdot \ldots \cdot (np)$$
2. You now can see $n$ factors which can be divided by $p$. What factors are those? If you divide each of those factors by $p$, you will recognize $n!$.
3. Modulo $p$, what is left equals $(p-1)!^n$. Convince yourself.
4. Use Wilson's Congruence to finish.

Answer 3

Well. $(np)! = 1*2*3*4*.........*np$ and if I point out a few of those terms we have.

$(np)! = 1*2*3*4*.....*(p-1)*(\color{blue}1\color{red}p)*(p+1)*.......*(2p-1)*(\color{blue}2\color{red}p)*(2p+1)*......*(3p-1)*(\color{blue}3\color{red}p)*(3p+1)*.........*(np-2)*(np-1)*(\color{blue}n\color{red}p)$

and rearangin those out we have.

$(np)! = \color{blue}{1*2*3*.....*n}*\color{red}{p*p*p*.....*p}*1*2*3*4*.....*(p-1)*(p+1)*.......*(2p-1)*(2p+1)*......*(3p-1)**(3p+1)*.........*(np-2)*(np-1)$

$=\color{blue}{n!}\color{red}{p^n}*1*2*3*4*.....*(p-1)*(p+1)*.......*(2p-1)*(2p+1)*......*(3p-1)*(3p+1)*.........*(np-2)*(np-1)$

Which means

$\frac {(np)!}{\color{blue}{n!}\color{red}{p^n}}=1*2*3*4*.....*(p-1)*(p+1)*.......*(2p-1)*(2p+1)*......*(3p-1)*(3p+1)*.........*(np-2)*(np-1)$ which is an integer.

Now.... Wilson's Theorem....

$1*2*3*4*.....*(p-1) \equiv -1 \pmod p$.

And as $kp +i \equiv i \pmod p$ then

$(kp+1)*......*((k+1)p -1)=$

$(kp+1)*.......*(kp + (p-1)) \equiv$

$1*.......*(p-1)\equiv$

$-1\pmod p$.

So......

$\frac {(np)!}{\color{blue}{n!}\color{red}{p^n}}=\color{green}{1*2*3*4*.....*(p-1)}*\color{orange}{(p+1)*.......*(2p-1)}*\color{purple}{(2p+1)*......*(3p-1)}*.....\color{gray}{((n-1)p+1)*.........*(np-2)*(np-1)}\equiv$

$\color{green}{1*2*3*4*.....*(p-1)}*\color{orange}{1*2*3*4*.....*(p-1)}*\color{purple}{1*2*3*4*.....*(p-1)}*.....\color{gray}{1*2*3*4*.....*(p-1)}\equiv$

$\color{green}{-1}*\color{orange}{-1}*\color{purple}{-1}*.....\color{gray}{-1}\equiv =(-1)^n\pmod p$.