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.
Problem
Source: 2012 Indonesia Round 2 TST 1 Problem 4
Tags: quadratics, floor function, search, modular arithmetic, induction, pigeonhole principle, number theory
29.02.2012 19:52
Decided to get off my lazy butt and finally write up my solution for this. First, note that if $p^2|n$ and $n$ works then so does $n/p$ for $p$ an odd prime, so for the moment we restrict our search to number who are not divisible by the square of any odd prime. Case 1: $4|n$ Note that $n=12$ is a solution. Now we take $n > 12$. Observe that a number is a quadratic residue modulo $4$ requires it not to be $3 \pmod{4}$. Hence $3$ cannot be a quadratic residue, and hence $3|n$. But then as $5$ is not a quadratic residue modulo $3$ we get $5|n$ if $n \ge 16$ which is easy to verify. Then $7|n$ because $7$ is not a square modulo $5$. Now with a few bases cases we prove this statement: Suppose the first $m$ primes $p_1, p_2, ..., p_m$ divide $n$ and $4|n$. Then $p_{m+1}|n$. To prove this, first note that we already have $m=4$. We will prove this by induction on $m$ with our base case being $m=4$. First, observe that $p_{m+1} \le 1 + \lfloor \sqrt{n} \rfloor$. This can be easily proven through proving $1 + \lfloor \sqrt{n} \rfloor \ge 2 p_m$ and then applying Chebyshev's Theorem. Hence we need $p_{m+1}$ to be a square modulo $p_i$ for all the primes $p_i$ below $p_{m+1}$. Note that $p_{m+1} \equiv 1 \pmod{4}$, so we have every odd primes below $p_{m+1}$ is a square modulo $p_{m+1}$ by Quadratic Reciprocity. This implies every odd number is a square modulo $p_{m+1}$. We then derive a contradiction because $0,4$ are also squares. Hence we must have $p_{m+1}|n$ and we have finished our induction. But this implies every prime divides $n$. This is obviously false, hence no further solutions for $4|n$ exist. Observe that if $v_2(n) = 1$ then $n/2$ works a well, so we will study $n$ odd for now. First we see that $2$ must be a quadratic residue modulo $n$, hence if $p|n$ then $p \equiv \pm 1 \pmod{8}$. Note that then $3,5 \nmid n$. Hence every prime which divides $n$ must also follow $p \equiv \pm 1 \pmod{12}, p \equiv \pm 1 \pmod{5}$. The first prime which satisfies these conditions is $p=71$, hence $n \ge 71$. First suppose $n$ is composite. Take the least prime factor $q$ of it. Observe that $q < \sqrt{n}$. But notice that all of $1,2,...,q-1$ are quadratic residues modulo $n$ and hence also quadratic residues modulo $q$. But this is a contradiction because that's to many quadratic residues, hence we have reached a contradiction and we are done with this case. Now suppose $n$ is prime. Let $n = a^2 + b$, then we have all $1 \le x \le 1+a$ are quadratic residues modulo $n$.
It follows the only values of $n$ are $\boxed{n = 1,2,12}$.
29.02.2012 20:01
Some problem: 6,22,30 works. It's late so I'm not sure about the correctness of your proof, but given the new values, seems like you accidentally skipped over some cases. And, well, it's late; why am I up?
29.02.2012 20:35
Oh wait oops I forgot to do the case of $v_2(n) = 1$ that was bad. My reduction of $n \implies n/2$ is actually wrong cause I'm dumb. Suppose $n = 2a$ where $a$ is odd and $n$ satisfies the problem. Suppose $a$ is composite with at least three prime factors. Using methods similar to above take the smallest prime divisor $p|n$ and derive a contradiction unless $p=3$. But then using $q$ derive a similar contradiction, except here consider which odd number which being multiplied by $4$ land in $[0,p), [2p, 3p)$ to derive a contradiction of to many quadratic residues. Hence $a$ has at most $2$ prime factors, one of which is $3$. Remark that $n=30$ works at this point. Now suppose $n = 6p$ works. For $p > 5$ we have a number $x \equiv 2 \pmod{3}$ satisfying $x < 1 + \lfloor \sqrt{n} \rfloor$, namely $x=5$, which is a contradiction. It is easy to check $n = 30 \cdot 3$ and $n = 30 \cdot 5$ don't work, hence $n=30$ is the only solution where $a$ has two prime factors. Now suppose $p$ is prime. Remark that $p=3,11$ satisfy the problem so now we will take $p > 11$. By the problem condition we have all the odd numbers up to $1 + \lfloor \sqrt{2p} \rfloor$ are quadratic residues modulo $p$. If $2$ is a quadratic residue then we can use the argument for $n = p$ above and derive a contradiction. Hence assume $2$ is not a quadratic residue modulo $p$. Perform the mapping of $x \to x/2$ modulo $p$. Note that in this image, a quadratic residue always maps to a non-residue. Hence we derive $\frac{p+1}{2}, \frac{p+3}{2},...,\frac{p + k}{2}$ are non-residues modulo $p$ where $k$ is the greatest odd number $\le 1 + \lfloor \sqrt{2p} \rfloor$. Remark that as there are $~\frac{p}{4}$ consecutive quadratic residues modulo $p$, the largest possible quadratic residue gap modulo $p$ is of length $4$ . Thus it follows $1 + \sqrt{2p} < 7 \implies p < 24$ and it remains to check cases... Everything not $\pm 1 \pmod{12}$ or $3$ breaks on $3$. Hence we only need to consider $p=3, 11, 13, 23$. $p=11$ works, $p=13$ breaks on $5$, $p=23$ breaks on $5$. Hence $p=3, 11$ are the only solutions and it is easy to show $n = 6 \cdot 3$ and $n = 22 \cdot 11$ are not solutions. Hence for the case of $v_2(n) = 1$, we have the solutions of $\boxed{n = 6,22,30}$. EDIT: There is an easier way to show if $n$ has more than two prime factors it doesn't work. I forgot that also the numbers in $[p+1, 2p)$ that are odd and not divisible by $3$ are also quadratic residues and then it's trivial. EDIT2: Oops the consecutive non-residues thing is completely wrong. I'll go find a patch later; for now just go observe the powerful theorems which instantly give a contradiction in that paper I linked to.