Baltic Way competition problems, 2013

Answer: Yes.

If some two of the first $n$ integers are congruent modulo $n$ then Mary can choose them consecutively and obtain a product divisible by $n$. Hence we may assume in the rest that the first $n$ integers written by the teacher are pairwise incongruent modulo $n$. This means that these $n$ integers cover all residues modulo $n$.

If $n$ is composite then Mary can find integers $k$ and $l$ such that $n = kl$ and $2 \le k \le l \le n-2$. Let Mary denote $a_1, a_2, a_3, a_4$ such that $a_1 \equiv k$, $a_2 \equiv 0$, $a_3 \equiv l+1$ and $a_4 \equiv 1$. The remaining numbers can be denoted in arbitrary order. The product is divisible by $n$ as the product of the first and the third factor is $(k-0) \cdot ((l+1)-1) = kl = n$.

If $n$ is prime then the numbers $c_i$, where $i = 0, 1, \dots, n-1$, cover all residues modulo $n$. Let Mary denote the numbers in such a way that $a_i \equiv c(n-i)$ for every $i = 1, \dots, n$. Then every factor in the product is congruent to $c$ modulo $n$, meaning that the product is congruent to $c^n$ modulo $n$. But $c^n \equiv c$ by Fermat's theorem, and Mary has done.