MathDB

2

Part of 2013 Serbia National Math Olympiad

Problems(1)

Binomial coefficients and complete residue system

Source: Serbian National Olympiad 2013, Problem 2

4/8/2013
For a natural number nn, set SnS_n is defined as: Sn={(nn),(2nn),(3nn),...,(n2n)}.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 nn, such that the set SnS_n is not complete residue system mod nn;
b) Prove that there are infinitely many composite numbers nn, such that the set SnS_n is complete residue system mod nn.
modular arithmeticnumber theorySerbia