Are there infinitely many $n$ such that $x^p\equiv r\bmod n$ has a solution for any $r$ and any odd $p$? I am looking to see if there are an infinite number of integers $n$ (not necessarily prime) with the following property:
There is always a solution $x$ to $x^p\equiv r\bmod n$ for any $r$ $≠$ $0$ and any odd integer $p$.
Is there a way to prove or disprove infinitely many integers $n$ with this property exist? I do not know where to start. Thanks.
 A: For there to be a solution $x$ to $x^p\equiv r\bmod n$, is to say that the function $f_{n,p}:\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z}$ (note: usually not a group or ring homomorphism) defined by $f_{n,p}(x)=x^p$ has $r$ in its image. Note that $0$ is always in the image of $f_{n,p}$ for any $p$.
Thus, if for some particular $p$ the equation $x^p\equiv r\bmod n$ has a solution for any $r\neq 0$, then $f_{n,p}$ has to be surjective. Since it is a function from a finite set to itself, that means that it must be bijective.
So, you are asking if there are infinitely many $n$ for which $f_{n,p}$ is bijective for all odd $p$.
If $\varphi(n)$ has any odd factor $p$, then the fact that $x^{\varphi(n)}\equiv 1\bmod n$ for all $x\in (\mathbb{Z}/n\mathbb{Z})^\times$ means that $x^p\equiv 1\bmod n$ has $p$ solutions, and therefore $f_{n,p}$ cannot be bijective. Thus, $\varphi(n)$ must be a power of $2$.
Since $\varphi(q^k)=q^{k-1}(q-1)$ for a prime $q$, and $\varphi$ is multiplicative, in order for $\varphi(n)$ to be a power of $2$, $n$ must have a prime factorization of the form $$2^kq_1\cdots q_r$$ where the primes $q_i$ are all of the form $2^{a_i}+1$ (hence, they must be Fermat primes, of which there are only five known). However, if $k>1$, then $f_{n,p}$ is not bijective for any $p>k$, since $$f_{n,p}(2q_1\cdots q_r)=2^pq_1^p\cdots q_r^p= 0\in\mathbb{Z}/n\mathbb{Z}$$ and $f_{n,p}(0)=0\in\mathbb{Z}/n\mathbb{Z}$.
Thus, $n$ must be of the form $q_1\cdots q_r$ where the $q_i$ are distinct, and can be either $2$ or a Fermat prime. If $n$ is of this form, then it is also sufficient for $f_{n,p}$ to be bijective for all odd $p$, since then $$\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}/q_1\mathbb{Z} \times\cdots \times \mathbb{Z}/q_r\mathbb{Z}=\mathbb{F}_{q_1}\times\cdots \times\mathbb{F}_{q_r}$$
is a product of fields each of whose group of units $(\mathbb{F}_{q_i})^\times$ is cyclic with order that is a power of $2$, and therefore has no elements of odd order.
As far as we know, there are only $64$ many such numbers:
$$2^{k_1}\cdot 3^{k_2}\cdot 5^{k_3}\cdot 17^{k_4}\cdot 257^{k_5}\cdot 65537^{k_6}$$
where each $k_i$ can be either $0$ or $1$.
