Problem 626

The answer is $n=1$ or any prime. We break this down into the following four steps.

1. $n$ has no square factor

Proof: If $p^2|n$, take $x=p$, then $p^2 \nmid x$ but $p^2|p^{p^2} = x$, a contradiction.

2. $n=1, p$ or $pq$, where $p$ and $q$ are primes

Proof: Since $n$ has no square factor, $n$ must be of the form $p_1p_2\cdots p_m$, hence the number of its divisors is $2^m$. But since the number of its divisors is not divisible by 8, we must have $m<3$, as claimed.

3. $n$ cannot be of the form $pq$

Proof: Without loss of generality assume $p < q$, and take $x$ to be a primitive root of $q$ (that is, the smallest positive integer $d$ such that $a^d \equiv a \mod n$). Based on $x^n \equiv x \mod q$, by minimality, we must have $q-1|n-1$, hence
$$q-1|n-1 = pq-1 = p(q-1) + (q-1) \Rightarrow q-1|p-1,$$
which contradicts the assumption that $p < q$.

4. Both $n=1$ and $n=p$ satisfy the conditions of the problem

Proof: $n=1$ is obvious, and $n=p$ is Fermat's Little Theorem.