A curious elementary number theory problem Find all $n$ satisfies $\forall k ((k,n)=1$ $\Rightarrow k^2 \equiv 1 (\mathrm{mod} n))$.
For example when n=8, k=1,3,5,7 satisfies the condition.
When n=24,k= 1,5,7,11,13,17,19 satisfies the condition.
When n=9, k=4,does not satisfy the condition.
My question is to find all n satisfying the condition.
 A: The Carmichael function of a positive integer $n$, denoted as $\lambda(n)$, is defined as the smallest positive integer $m$ such that
$$a^m \equiv 1 \pmod n$$
for every integer $a$ that is coprime to $n$. So what you are asking is equivalent to the question: what are the list of $n$ such that $\lambda(n) = 1$ or $2$. 
The Carmichael function of $n$ can be computed by the values on its prime factorization. More precisely, if one express $n$ as a product of its prime factors $p_1^{e_1} p_2^{e_2} \ldots p_r^{e_r}$,
one has
$$\lambda(n) = \lambda(p_1^{e_1} p_2^{e_2} \ldots p_r^{e_r}) = 
\text{lcm}(\lambda(p_1^{e_1}), \lambda(p_2^{e_2}), \ldots, \lambda(p_r^{e_r}) )$$
This relation can be proved easily using Chinese remainder theorem.
When $n$ has the form of a prime power $p^e$, we know:
$$\lambda(p^e) = \begin{cases}
\varphi(p^e) = 2^{e-1},& p = 2, e \le 2.\\
\frac12\varphi(p^e) = 2^{e-2}, & p = 2, e > 2\\
\varphi(p^e) = (p-1)p^{e-1},& p \ne 2
\end{cases}\tag{*1}$$
where $\varphi(n)$ is the Euler totient function. 
From this, it is easy to see in order for $\lambda(n)$ to be $1$ or $2$. All of its prime factors $p^e$ must have $\lambda(p^e) = 1$ or $2$. Look back at $(*1)$, one find
$$p^e = 1, 2, 4, 8 \text{ or } 3\quad\implies\quad n = 1, 2, 4, 8 \text{ or } 3, 6, 12, 24.$$
A: Your question is equivalent to the following: find all $n$'s such that all element of $(\mathbb Z/n\mathbb Z)^*$ have order at most $2$. So a necessary condition is that $\varphi(n)$ is a power of $2$, where $\varphi$ is Euler's totient function. This shows that $n$ has the form $2^kp_1\ldots p_m$ where  the $p_i$'s are distinct primes (of the form $2^{r_i}+1$) and $k\in \mathbb N$. Now by the Chinese remainder theorem, $(\mathbb Z/n\mathbb Z)^*\simeq (\mathbb Z/2^k\mathbb Z)^*\times (\mathbb Z/p_1\mathbb Z)^*\times\ldots\times (\mathbb Z/p_m\mathbb Z)^*$. So any element $x\in (\mathbb Z/n\mathbb Z)^*$ must have order at most $2$ in every factor. Suppose $k\geq 4$. Then you must have that every element of $(\mathbb Z/2^k\mathbb Z)^*$ different from $1$ has order $2$, namely that $(2r+1)^2\equiv 1\bmod 2^k$ for every natural $r$, which implies $2^k\mid 4r(r+1)$. This is clearly impossible whenever $r=1$ for example. Therefore $k\leq 3$.
On the other hand, the group $(\mathbb Z/p_i\mathbb Z)^*$ has exactly $\frac{p_i-1}{2}$ different quadratic residues, while you must have only $1$ in your case. This shows that $\frac{p_i-1}{2}=1$, namely $p=3$.
All in all, we proved that the only possible $n$'s are of the form $3^{\varepsilon}2^k$ for $\varepsilon\in \{0,1\}$ and $k\in \{0,1,2,3\}$.
Now just check by hand which of these few cases are possible!
