Problem

Source: 2012 Indonesia Round 2 TST 1 Problem 4

Tags: quadratics, floor function, search, modular arithmetic, induction, pigeonhole principle, number theory



Determine all natural numbers $n$ such that for each natural number $a$ relatively prime with $n$ and $a \le 1 + \left\lfloor \sqrt{n} \right\rfloor$ there exists some integer $x$ with $a \equiv x^2 \mod n$. Remark: "Natural numbers" is the set of positive integers.