For a natural number $n$, set $S_n$ is defined as: \[S_n = \left \{ {n\choose n}, {2n \choose n}, {3n\choose n},..., {n^2 \choose n} \right \}.\] a) Prove that there are infinitely many composite numbers $n$, such that the set $S_n$ is not complete residue system mod $n$; b) Prove that there are infinitely many composite numbers $n$, such that the set $S_n$ is complete residue system mod $n$.
Problem
Source: Serbian National Olympiad 2013, Problem 2
Tags: modular arithmetic, number theory, Serbia
09.04.2013 02:54
For part b., note that $\dbinom{ap^2}{p^2} \equiv \dbinom{a}{1} \equiv a \pmod{p^2}$ by Wolstenholme's Theorem for $p > 3$, so it follows for $n$ the square of a prime it forms a complete residue system. Part a. will hopefully come later.
09.04.2013 13:12
For part a) take $n=2p$ and note that $\binom{pn}{n},\binom{2pn}{n}$ and $\binom{\frac{p+1}{2}n}{n}$ are all divisible by $p$.
26.01.2015 00:04
For part a) you can take $n=2p$ where $p \equiv 3 (mod 4)$ and use Legendre's formula to get $ \binom{\frac{p+1}{2}n}{n} $ is divisible by $n$. Since $\binom{n^2}{n}$ is divisible by $n$, we are done.
05.01.2018 22:57
agreed with dr civot for a) n=2p p=3 (mod4) and for b) n=p
02.08.2020 00:31
$(a)$ Suppose $n=2p$ for some odd prime number $p$. Then $$\binom{n^2}{n} = \binom{4p^2}{2p}=\frac{4p^2}{2p}\binom{4p^2-1}{2p-1} = 2p\binom{4p^2-1}{2p-1} \equiv 0 \pmod{2p}$$and \begin{align*} \binom{pn}{n} = \binom{2p^2}{2p}&=\frac{2p^2(2p^2-1)(2p^2-2)}{2p(2p-1)(2p-2)}\binom{2p^2-3}{2p-3} =\frac{p(p+1)(2p^2-1)}{2p-1}\binom{2p^2-3}{2p-3} \equiv 0 \pmod{2p} \end{align*}where we used the fact that $(2p-1, 2p) = 1$. This means there are at least two elements of $S_{2p}$ divisible by $2p$. So $S_{2p}$ is not a full residue system modulo $2p$. $(b)$ Let $n=p^2$ for some odd prime number $p$. Then \begin{align*} \binom{kp^2}{p^2} &=\frac{((k-1)p^2 + 1)\cdot ((k-1)p^2 + 2) \cdots ((k-1)p^2 + p^2 - 1)(kp^2)}{1 \cdot 2 \cdot 3\cdots (p^2-1)\cdot p^2}\\ &= \frac{kp^2\displaystyle\prod_{j=1}^{p-1}((k-1)p^2+jp)\displaystyle\prod_{j=0}^{p-1}\prod_{s=1}^{p-1}((k-1)p^2+jp+s))}{p^2\displaystyle\prod_{j=1}^{p-1}(jp)\displaystyle\prod_{j=0}^{p-1}\prod_{s=1}^{p-1}(jp+s)}\\ &\equiv \frac{k\displaystyle\prod_{j=1}^{p-1}((k-1)p+j)\displaystyle\prod_{j=0}^{p-1}\prod_{s=1}^{p-1}(jp+s))}{\displaystyle\prod_{j=1}^{p-1}j\displaystyle\prod_{j=0}^{p-1}\prod_{s=1}^{p-1}(jp+s)}\equiv k \pmod{p^2} \end{align*}where we used the fact that \begin{align*} \displaystyle\prod_{j=1}^{p-1}((k-1)p+j) &\equiv (k-1)p\cdot\sum_{j=0}^{p-1}j + \displaystyle\prod_{j=1}^{p-1}j \equiv (k-1)p\cdot\frac{p(p-1)}{2} + \displaystyle\prod_{j=1}^{p-1}j\equiv \displaystyle\prod_{j=1}^{p-1}j \pmod{p^2} \end{align*}So $S_{p^2}$ is a full residue system modulo $p^2$.
16.04.2022 21:43
$(a)$ $n=2p$ $p\equiv 3$(mod4)