# Prove that $\binom{ap}{p} \equiv a \pmod{ap}$

Let $N = ap$ be a composite positive integer, where $a > 1$ is a positive integer and $p$ is a prime. Prove that $$\binom{ap}{p} \equiv a \pmod{ap}.$$

We have $$\binom{ap}{p} = \dfrac{ap(ap-1) \cdots (ap-(p-1))}{p!} = \dfrac{a(ap-1)(ap-2) \cdots (ap-(p-1))}{(p-1)!}.$$ If $p$ is the smallest prime factor of $ap$, then $(p-1)!$ has an inverse modulo $ap$. Also, $(ap-1)(ap-2) \cdots (ap-(p-1)) \equiv (-1)^{p-1} (p-1)!$. If $p = 2$, then $$\binom{ap}{p} \equiv a \cdot \dfrac{-(p-1)!}{(p-1)!} \equiv -a \equiv a \pmod{ap}.$$ Otherwise, if $p > 2$ is odd then $$\binom{ap}{p} \equiv a \cdot \dfrac{(p-1)!}{(p-1)!} \equiv a \pmod{ap}.$$ How do we prove it in the case that $p$ is not the smallest prime factor of $ap$?

• Will $\begin{pmatrix} ap \\ p \end{pmatrix} = \begin{pmatrix} ap \\ ap-p \end{pmatrix}$ help? Oct 23 '17 at 20:26
• $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$? Oct 23 '17 at 20:26
• @rtybase How do we use that? Oct 23 '17 at 20:42

The proof is for $p>2$! Considering $$\binom{ap}{p}=\frac{ap}{p}\binom{ap-1}{p-1} \tag{1}$$ and $$ap-1 \equiv -1 \pmod{p}$$ $$ap-2 \equiv -2 \pmod{p}$$ $$...$$ $$ap-p+1 \equiv -p+1 \pmod{p}$$ we obtain $$(ap-1)(ap-2)...(ap-p+1) \equiv (-1)^{p-1}(p-1)! \equiv (p-1)! \pmod{p} \tag{2}$$ But $$\binom{ap-1}{p-1}=Q \in \mathbb{N} \Rightarrow (ap-1)(ap-2)...(ap-p+1)=Q\cdot (p-1)!$$ Substituting in $(2)$: $$Q\cdot (p-1)! \equiv (p-1)! \pmod{p}$$ But $p \nmid (p-1)!$ (and $p$-prime), thus: $$Q \equiv 1 \pmod{p}$$ Or $$p \mid (Q-1) \Rightarrow ap \mid (aQ-a) \Rightarrow aQ\equiv a \pmod{ap}$$ which, considering $(1)$, is equivalent to $$a\binom{ap-1}{p-1}=aQ \equiv a \pmod{ap} \Leftrightarrow \frac{ap}{p}\binom{ap-1}{p-1} \equiv a \pmod{ap} \Leftrightarrow\\ \binom{ap}{p} \equiv a \pmod{ap}$$

• How did you get $Q \equiv 1 \pmod{ap}$? If $p$ is not the smallest prime factor of $ap$ then $\gcd(ap,(p-1)!) > 1$. Oct 23 '17 at 21:41
• From $Q\cdot (p-1)! \equiv (p-1)! \pmod{ap} \Rightarrow ap \mid (p-1)!(Q-1)$ ... I have a typo ... fixing ... Oct 23 '17 at 21:50
• @user19405892 fixed ... a bit longer, but hopefully with enough details Oct 23 '17 at 21:56

using Lucas'Theorem, suppose $a\equiv k \pmod p$, we will have:

$\binom{ap}{p} \equiv\binom{k}{1} =k \equiv a \pmod p$

We also have

$\binom{ap}{p} = \dfrac{a(ap-1)(ap-2) \cdots (ap-(p-1))}{(p-1)!} = a\binom{ap-1}{p-1} \equiv 0 \pmod a$

Let $\binom{ap}{p}=Zp+a$, so $a|Z$, so

$Zp+a=Kap+a \equiv a \pmod {ap}$