4
$\begingroup$

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

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

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Oct 23 '17 at 21:41
  • $\begingroup$ From $Q\cdot (p-1)! \equiv (p-1)! \pmod{ap} \Rightarrow ap \mid (p-1)!(Q-1)$ ... I have a typo ... fixing ... $\endgroup$
    – rtybase
    Oct 23 '17 at 21:50
  • $\begingroup$ @user19405892 fixed ... a bit longer, but hopefully with enough details $\endgroup$
    – rtybase
    Oct 23 '17 at 21:56
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.