Skip to main content
1 of 2
Charles
  • 9.1k
  • 1
  • 38
  • 76

Mod n, are all higher powers also lower powers?

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 then there is some $p \le H(n)$ such that $r$ is a $p$-th power mod $n$.

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.)

Charles
  • 9.1k
  • 1
  • 38
  • 76