Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Question

Started solving this problem:

$$ (a+b)^p \equiv a^p+b^p \pmod{p}$$
where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $

After a few implications I arrived to this $$ i! \mid (p-1)\cdot(p-2)\cdots(p-i+1) ,\quad i < p$$

Tried some special cases with no progress.

Answer 1

Right, you're probably wanting to show that $p$ divides the binomial coefficient $$\binom{p}{i}=\frac{p!}{i!(p-i)!}=p\cdot\frac{(p-1)\cdots(p-i+1)}{i!}$$ and hence want to show that the fraction is actually an integer.

Here's one approach: Let $m=(p-1)\cdots(p-i+1)$, and let $n=pm$. We know that $i!\mid n$ because binomial coefficients are integers, and $\binom{p}{i}=\frac{n}{i!}$. Because $i!\mid pm$, it will suffice to show that $\gcd(i!,p)=1$ to conclude that $i!\mid m$.

(It is a general fact that $a\mid bc$ and $\gcd(a,c)=1$ $\implies$ $a\mid b$.)

But the fact that $\gcd(i!,p)=1$ is clear, because $i!$ is the product of numbers all of which are strictly less than $p$, and therefore cannot have any factor of $p$ in them (since $p$ is prime).

Answer 2

Note that $$\frac{p(p-1)(p-2)\cdots(p-i+1)}{i!}=\binom pi$$ that is, an integer. And it is multiple of $p$ since $p$ is not a factor of $i!$.

Answer 3

If you already know Fermat's little theorem, then:

$$(a+b)^p\equiv (a+b)\equiv (a^p+b^p)\pmod{\! p}$$

and you're done. If not, then by Binomial theorem$$(a+b)^p-a^p-b^p=\binom{p}{1}a^{p-1}b+\binom{p}{2}a^{p-2}b^2+\cdots+\binom{p}{p-1}ab^{p-1},$$

which is divisible by $p$ (and you're done), because $p\mid \binom{p}{i}$ for any $1\le i\le p-1$.

This is because $\binom{p}{i}=\frac{p!}{(p-i)!i!}$ - the numerator is divisible by $p$ and the denominator is not, so the fraction (which is known to be an integer) is divisible by $p$.

Answer 4

Define falling factorial powers by $ n^{\underline{m}} = n (n - 1) \dotsm (n - m + 1) $.

By induction, prove that:

$$\sum_{0 \le k \le n} k^{\underline{m}} = \frac{n^{\underline{m + 1}}}{m + 1}$$

Now we prove that $k!$ divides any product of $k$ consecutive integers, i.e., it divides $n^{\underline{k}}$ for all $n$ by induction on $k$.

Base: For $k = 0$ this reduces to $1 \mid n$, which is always true.

Induction: We know from the above that $n^{\underline{k + 1}} = (k + 1) \sum_{0 \le r \le n} r^{\underline{k}}$. By induction, each of the terms of the sum is divisible by $k!$, so the right hand side is divisible by $(k + 1) k! = (k + 1)!$.