IMO Hk TST

Number theory Difficulty 8.0 National Olympiad, round 2 Prove it Hong Kong

Let $p$ be a prime number and $n$ a positive integer such that $n \ge p$ . Show that $\binom{n}{p} - \lfloor \frac{n}{p} \rfloor$ is divisible by $p$ . (Here the combinatorial symbol $\binom{n}{p} = \frac{n!}{p!(n-p)!}$ and $\lfloor x \rfloor$ stands for the largest integer less than or equal to $x$ .)

Solution

This is an immediate consequence of Lucas' theorem. We give an elementary proof as follows.

Let $n = ap + r$ where $0 \le r \le p - 1$ . Then we have
$\binom{n}{p} = \frac{n(n-1)\cdots(n-p+1)}{p!} \\ = \frac{(ap+r)(ap+r-1)\cdots(ap+1)(a)(ap-1)(ap-2)\cdots(ap+r-p+1)}{(p-1)!}$
Note that the numerator is congruent to
$r(r-1)\cdots(1)(a)(p-1)(p-2)\cdots(r+1) = a \cdot (p-1)!$
modulo $p$ . Therefore, we find that
$\binom{n}{p} \equiv a = \left\lfloor \frac{n}{p} \right\rfloor \pmod{p}.$
This proves the desired result.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.