, 2011

Let $N=\{1,2, \ldots, n-1\}$. For $a, b \in N$, we say that $b$ follows $a$ if there exists an integer $g$ such that $b \equiv g^{a} (\bmod n)$ and denote this property as $a \rightarrow b$. This way we have a directed graph with $N$ as set of vertices. If $a_{1}, \ldots, a_{n-1}$ is a permutation of $1,2, \ldots, n-1$ such that $a_{1} \rightarrow a_{2} \rightarrow \ldots \rightarrow a_{n-1} \rightarrow a_{1}$ then this is a Hamiltonian cycle in the graph.

Step I. First consider the case when $n$ is composite. Let $n=p_{1}^{\alpha_{1}} \ldots p_{s}^{\alpha_{s}}$ be its prime factorization. All primes $p_{i}$ are odd.

Suppose that $\alpha_{i}>1$ for some $i$. For all integers $a, g$ with $a \geq 2$, we have $g^{a} \not \equiv p_{i} \left(\bmod p_{i}^{2}\right)$, because $g^{a}$ is either divisible by $p_{i}^{2}$ or it is not divisible by $p_{i}$. It follows that in any Hamiltonian cycle $p_{i}$ comes immediately after $1$. The same argument shows that $2 p_{i}$ also should come immediately after $1$, which is impossible. Hence, there is no Hamiltonian cycle in the graph.

Now suppose that $n$ is square-free. We have $n=p_{1} p_{2} \ldots p_{s}>9$ and $s \geq 2$. Assume that there exists a Hamiltonian cycle. There are $\frac{n-1}{2}$ even numbers in this cycle, and each number which follows one of them should be a quadratic residue modulo $n$. So, there should be at least $\frac{n-1}{2}$ nonzero quadratic residues modulo $n$. On the other hand, for each $p_{i}$ there exist exactly $\frac{p_{i}+1}{2}$ quadratic residues modulo $p_{i}$; by the Chinese Remainder Theorem, the number of quadratic residues modulo $n$ is exactly $\frac{p_{1}+1}{2} \cdot \frac{p_{2}+1}{2} \cdot \ldots \cdot \frac{p_{s}+1}{2}$, including $0$. Then we have a contradiction by
$$\frac{p_{1}+1}{2} \cdot \frac{p_{2}+1}{2} \cdot \ldots \cdot \frac{p_{s}+1}{2} \leq \frac{2 p_{1}}{3} \cdot \frac{2 p_{2}}{3} \cdot \ldots \cdot \frac{2 p_{s}}{3}=\left(\frac{2}{3}\right)^{s} n \leq \frac{4 n}{9}<\frac{n-1}{2} .$$
This proves the "if"-part of the problem.

Step II. Now suppose that $n$ is prime. For any $a \in N$, denote by $\nu_{2}(a)$ the exponent of $2$ in the prime factorization of $a$, and let $\mu(a)=\max \left\{t \in[0, k] \mid 2^{t} \rightarrow a\right\}$.

Lemma. For any $a, b \in N$, we have $a \rightarrow b$ if and only if $\nu_{2}(a) \leq \mu(b)$.

Proof. Let $\ell=\nu_{2}(a)$ and $m=\mu(b)$.

Suppose $\ell \leq m$. Since $b$ follows $2^{m}$, there exists some $g_{0}$ such that $b \equiv g_{0}^{2^{m}} (\bmod n)$. By $\operatorname{gcd}(a, n-1)=2^{\ell}$ there exist some integers $p$ and $q$ such that $p a-q(n-1)=2^{\ell}$. Choosing $g=g_{0}^{2^{m-\ell} p}$ we have $g^{a}=g_{0}^{2^{m-\ell} p a}=g_{0}^{2^{m}+2^{m-\ell} q(n-1)} \equiv g_{0}^{2^{m}} \equiv b (\bmod n)$ by Fermat's theorem. Hence, $a \rightarrow b$.

To prove the reverse statement, suppose that $a \rightarrow b$, so $b \equiv g^{a} (\bmod n)$ with some $g$. Then $b \equiv\left(g^{a / 2^{\ell}}\right)^{2^{\ell}}$, and therefore $2^{\ell} \rightarrow b$. By the definition of $\mu(b)$, we have $\mu(b) \geq \ell$. The lemma is proved.

Now for every $i$ with $0 \leq i \leq k$, let
$$\begin{aligned} A_{i} & =\left\{a \in N \mid \nu_{2}(a)=i\right\}, \\ B_{i} & =\{a \in N \mid \mu(a)=i\}, \\ \text{and } C_{i} & =\{a \in N \mid \mu(a) \geq i\}=B_{i} \cup B_{i+1} \cup \ldots \cup B_{k} . \end{aligned}$$
We claim that $\left|A_{i}\right|=\left|B_{i}\right|$ for all $0 \leq i \leq k$. Obviously we have $\left|A_{i}\right|=2^{k-i-1}$ for all $i= 0, \ldots, k-1$, and $\left|A_{k}\right|=1$. Now we determine $\left|C_{i}\right|$. We have $\left|C_{0}\right|=n-1$ and by Fermat's theorem we also have $C_{k}=\{1\}$, so $\left|C_{k}\right|=1$. Next, notice that $C_{i+1}=\left\{x^{2} \bmod n \mid x \in C_{i}\right\}$. For every $a \in N$, the relation $x^{2} \equiv a (\bmod n)$ has at most two solutions in $N$. Therefore we have $2\left|C_{i+1}\right| \leq\left|C_{i}\right|$, with the equality achieved only if for every $y \in C_{i+1}$, there exist distinct elements $x, x' \in C_{i}$ such that $x^{2} \equiv x'^{2} \equiv y (\bmod n)$ (this implies $x+x'=n$). Now, since $2^{k}\left|C_{k}\right|=\left|C_{0}\right|$, we obtain that this equality should be achieved in each step. Hence $\left|C_{i}\right|=2^{k-i}$ for $0 \leq i \leq k$, and therefore $\left|B_{i}\right|=2^{k-i-1}$ for $0 \leq i \leq k-1$ and $\left|B_{k}\right|=1$.

From the previous arguments we can see that for each $z \in C_{i} (0 \leq i<k)$ the equation $x^{2} \equiv z^{2} (\bmod n)$ has two solutions in $C_{i}$, so we have $n-z \in C_{i}$. Hence, for each $i=0,1, \ldots, k-1$, exactly half of the elements of $C_{i}$ are odd. The same statement is valid for $B_{i}=C_{i} \backslash C_{i+1}$ for $0 \leq i \leq k-2$. In particular, each such $B_{i}$ contains an odd number. Note that $B_{k}=\{1\}$ also contains an odd number, and $B_{k-1}=\left\{2^{k}\right\}$ since $C_{k-1}$ consists of the two square roots of $1$ modulo $n$.

Step III. Now we construct a Hamiltonian cycle in the graph. First, for each $i$ with $0 \leq i \leq k$, connect the elements of $A_{i}$ to the elements of $B_{i}$ by means of an arbitrary bijection. After performing this for every $i$, we obtain a subgraph with all vertices having in-degree $1$ and outdegree $1$, so the subgraph is a disjoint union of cycles. If there is a unique cycle, we are done. Otherwise, we modify the subgraph in such a way that the previous property is preserved and the number of cycles decreases; after a finite number of steps we arrive at a single cycle.

For every cycle $C$, let $\lambda(C)=\min _{c \in C} \nu_{2}(c)$. Consider a cycle $C$ for which $\lambda(C)$ is maximal. If $\lambda(C)=0$, then for any other cycle $C'$ we have $\lambda\left(C'\right)=0$. Take two arbitrary vertices $a \in C$ and $a' \in C'$ such that $\nu_{2}(a)=\nu_{2}\left(a'\right)=0$; let their direct successors be $b$ and $b'$, respectively. Then we can unify $C$ and $C'$ to a single cycle by replacing the edges $a \rightarrow b$ and $a' \rightarrow b'$ by $a \rightarrow b'$ and $a' \rightarrow b$.

Now suppose that $\lambda=\lambda(C) \geq 1$; let $a \in C \cap A_{\lambda}$. If there exists some $a' \in A_{\lambda} \backslash C$, then $a'$ lies in another cycle $C'$ and we can merge the two cycles in exactly the same way as above. So, the only remaining case is $A_{\lambda} \subset C$. Since the edges from $A_{\lambda}$ lead to $B_{\lambda}$, we get also $B_{\lambda} \subset C$. If $\lambda \neq k-1$ then $B_{\lambda}$ contains an odd number; this contradicts the assumption $\lambda(C)>0$. Finally, if $\lambda=k-1$, then $C$ contains $2^{k-1}$ which is the only element of $A_{k-1}$. Since $B_{k-1}=\left\{2^{k}\right\}=A_{k}$ and $B_{k}=\{1\}$, the cycle $C$ contains the path $2^{k-1} \rightarrow 2^{k} \rightarrow 1$ and it contains an odd number again. This completes the proof of the "only if"-part of the problem.