
N1. Determine all integers $n \geq 3$ whose decimal expansion has less than 20 digits, such that every quadratic non-residue modulo $n$ is a primitive root modulo $n$.

An integer $a$ is a quadratic non-residue modulo $n$, if there is no integer $b$ such that $a-b^{2}$ is divisible by $n$. An integer $a$ is a primitive root modulo $n$, if for every integer $b$ relatively prime to $n$ there is a positive integer $k$ such that $a^{k}-b$ is divisible by $n$.


Solution 1. The required numbers are the first five Fermat numbers: $n=2^{2^{k}}+1, k=0,1, \ldots, 4$. The main thrust is that an integer $n \geq 3$ satisfies the second condition in the statement if and only if $n$ is a Fermat prime. The first five Fermat numbers are indeed prime (and have at most five decimal digits), the sixth is not (Euler showed it divisible by 641), and the higher rank Fermat numbers all have at least 20 decimal digits: if $k \geq 6$, then $F_{k}=2^{2^{k}}+1 \geq 2^{2^{6}}+1=$ $2^{4} \cdot\left(2^{10}\right)^{6}+1>2^{4} \cdot\left(10^{3}\right)^{6}+1=16 \cdot 10^{18}+1>10^{19}$.

Since a primitive root modulo $n$ is necessarily a quadratic non-residue modulo $n$ (otherwise, the multiplicative order of the former would be at most $\phi(n) / 2)$, and for a Fermat prime the number of primitive roots and the number of quadratic non-residues are equal (for a Fermat prime $F_{k}$ both are $2^{k}$ ), all Fermat primes satisfy the second condition in the statement.

To prove the converse, we deliberately ignore the characterisation of moduli admitting primitive roots, and first show that if all quadratic non-residues modulo $n$ are relatively prime to $n$, then $n$ is prime. To this end, let $U$ be the set of integers in the range $0,1, \ldots, n-1$ that are relatively prime to $n$, so $|U|=\phi(n)$, and let $S=\{0,1, \ldots, n\} \backslash U$. By hypothesis, all quadratic non-residues modulo $n$ are in $U$, so all of $S$ are quadratic residues modulo $n$. Therefore, the function $f: S \rightarrow S, f(k) \equiv k^{2}(\bmod n)$ is surjective, and hence injective. Since $f(k)=f(n-k)$ for all $k$, it follows that $2 k \equiv 0(\bmod n)$ for all $k$ in $S$, so either $k=0$ or the additive order of $k$ modulo $n$ is 2 . Since $\left(\mathbb{Z}_{n},+\right)$ has at most two elements of order at most 2 , it follows that $n-\phi(n)=n-|U|=|S| \leq 2$. Recall that $n \geq 3$, so $\phi(n)$ is even. If $n-\phi(n)=2$, then $n$ is even, so $\phi(n) \leq n / 2$, in which case $n=4$ and $f$ is not injective. Consequently, $\phi(n)=n-1$, and therefore $n$ is prime. Hence the number of quadratic non-residues is $(n-1) / 2$, and the number of primitive roots is $\phi(n-1)$.

If, in addition, every quadratic non-residue is a primitive root, then $\phi(n-1) \geq(n-1) / 2$. Since $n$ is odd, it follows that $\phi(n-1) \leq(n-1) / 2$, so $\phi(n-1)=(n-1) / 2$, in which case $n-1$ is a power of 2 ; that is, $n$ is a Fermat prime: $n=2^{2^{k}}+1$, where $k$ is a non-negative integer.
