Since there are only finitely many residues mod $n$, there is some function $H(n) \le n$ such that for all integers $n>1$, $r$, and $e>H(n)$, if $r$ is an $e$-th power mod $n$ then there is some $p \le H(n)$ such that $r$ is a $p$-th power mod $n$. (As usual, $p$ denotes a prime number.)


Is $H\_0$ such a function, where $H\_0(n)=p$ is defined by
$$
(p-1)\# \le n \le p\#
$$
with the primorial $x\#=\prod\_{p\le x}p=\exp(\vartheta(x))$?


For example, 10 is not a square, cube, or fifth or seventh power mod 36, so this would say that it is not an $e$-th power for any $e>7$.


Are any such residues coprime to their modulus? (I assume not.)



Mod n, are all higher powers also lower powers?
So your question is as follows: let $n$ be a positive integer, $q$ the smallest prime such that $q\sharp > n$, $e>q$ be an integer and $r$ be an $e$-th power mod $n$. Then is $r$ a $p$-th power for some $p\leq q$?


In general, *no*. Take a large prime $q$ and $n$ be the greatest power of $2$ less than $q\sharp$: then $n \geq e^{(1+o(1))q}$ by the PNT, so we can find (PNT again) some prime $s>q$ such that $2^s < n$. Take $r=2^s$ and $e=s$, assume that $r$ is a $p$-th power for some $p \leq q$. But this implies that the $2$-adic valuation of $r$ is divisible by $p$, which is impossible.




---


Now, let’s state a simple condition under which the statement *holds* (albeit for mostly trivial reasons).


Note that $q\sharp= e^{\theta(q)} \in [c^{-1},c]e^q$ where $c=e^{0.007q/\ln{q}}$ (by eg [this](https://en.m.wikipedia.org/wiki/Chebyshev_function)): so if $n \geq 6$, we see that $n \leq q\sharp < 3^q$.


Our assumption is that we also have $v\_2(n) \leq q$.


If $e$ has a prime divisor $p \leq q$, then $p$ works. Otherwise, replacing $e$ with one of its prime divisors, we can assume that $e$ is prime.


As $\varphi(n) < n \leq q\sharp$, there is some $p\leq q$ not dividing $\varphi(n)$, so that taking the $p$-th power in $(\mathbb{Z}/d\mathbb{Z})^{\times}$ is an isomorphism for all $d |n$.


Moreover, if $s$ is a prime power dividing $n$ and coprime to $n/s$, such that $r$ and $s$ are not coprime, then the valuation of $s$ is at most $q$ (by the assumption), so the only noninvertible $e$-th power mod $s$ is zero (every noninvertible element to the $e$-th power is zero). Thus $r$ is zero mod $s$ (hence a $p$-th power).


It follows by CRT that $s$ is a $p$-th power mod $n$, QED.


