We define a $k^{\text{th}}$ power residue modulo $n$ to be an integer $a$ coprime to $n$ such that there exists an integer $x$ satisfying $$x^k\equiv a\pmod{n}.$$ A fundamental question that we can ask is:
Given fixed integers $k\ge 2$ and $n\ge 2,$ how many $k^{\text{th}}$ power residues modulo $n$ exist?
A variant of the Chinese remainder theorem for $k^{\text{th}}$ powers shows that this is the product of the answers when the moduli are the the maximal prime powers in the prime factorization of $n.$ For powers of odd primes $p,$ this is solved by a variant of Euler's criterion (see section 6.5 of Vinogradov's Elements of Number Theory).
But what about when the modulus is a power of $2$? Unfortunately, Vinogradov's proof in the odd prime case uses primitive roots, which does not exist modulo powers of $2$ that are greater than $4=2^2$. In the quadratic case, a paper of Stangl provides a formula on p.287-288. His method uses the difference of squares factorization and other ideas that do not readily extend to higher powers, at least not as far as I can tell.
Please let me know if there is a formula for the number of $k^{\text{th}}$ power residues modulo $2^n$ for fixed integers $k\ge 2$ and $n\ge 3$.
The answer might have to do with the structure of $(\mathbb{Z}/2^n \mathbb{Z})^{\times}$ but I'm not sure.
Best Answer
Here is the full proof based on ArturoMagidin's comments on the original post (this proof appears in a book that I am writing and a paper that I wrote that is currently under review). Let $k\ge 2$ and $n\ge 3$ be fixed integers. As I wrote in the proof here, the invertible elements modulo $2^n$ are given by the $\varphi(2^n) = 2^{n-1}$ distinct elements of $$S=\left\{\pm 5^k : k\in [2^{n-2}]\right\},$$ where $[t]$ denotes $\{1,2,\ldots, t\}$. We will show that $$|S_k (2^n)| = \begin{cases} \hfill \dfrac{2^{n-2}}{(k, 2^{n-2})} &\text{ if } 2\mid k\\ \hfill 2^{n-1} &\text{ if } 2\nmid k \end{cases}. $$ where $S_k (n)$ denotes the set of reduced $k^{\text{th}}$ power residue classes modulo $n$, meaning those residue classes that are coprime to $n$.
We will use the fact that, for $k\ge 2$, the $k^{\text{th}}$ power map modulo an integer $n\ge 2$ is bijective on the set of reduced residue classes modulo $n$ if and only if $(k,\varphi(n))=1.$ Let $k=2^j m,$ where $m$ is odd. If $j=0,$ then the exponent $k$ is odd and so coprime to $2^n.$ By the aforementioned fact, all integers coprime to $2^n$ are in $S_k (2^n),$ so $|S_k (n)| = 2^{n-1}.$ Now we can assume that $j\ge 1.$ We can think of the $k^{\text{th}}$ power map as taking a power of $m$ of each element of $S$ followed by taking a power of $2^j$ of each element of $S.$ Again by the aforementioned fact, the first map is irrelevant because it is a bijection on $S.$ What really matters is the application of the second map to $$S=\left\{\pm 5^k : k\in [2^{n-2}]\right\}.$$ Since $j\ge 1,$ we can remove any negative signs and we get the set $$T=\left\{ (5^k)^{2^j} : k\in [2^{n-2}]\right\}.$$ Not every $(5^k)^{2^j}$ is necessarily distinct modulo $2^n$ so we have to determine to amount of duplication, or rather the number of distinct elements defined as that will be the cardinality of $S_k (2^n)$. We rewrite each element as $(5^{2^j})^k$ for $1\le k\le 2^{n-2}.$ By the standard proof of the fact that there is no primitive root modulo powers of $2$ (which proves that odd integers have order less than or equal to $2^{n-2}$ modulo $2^n$), we find that $$(5^{2^j})^{2^{n-2}} \equiv (5^{2^{n-2}})^{2^j}\equiv 1^{2^j} \equiv 1\pmod{2^n},$$ and higher powers of $5^{2^j}$ cycle through lower powers. So all elements generated by the powers of $5^{2^j}$ are in $T,$ in addition to every element of $T$ being a power of $5^{2^j}.$ Thus, the number of distinct elements of $T$ modulo $2^n,$ and therefore the cardinality of $S_k (2^n),$ is $$|S_k (2^n)| =\text{ord}_{2^n}(5^{2^j})=\frac{\text{ord}_{2^n}(5)}{(2^j, \text{ord}_{2^n}(5))}=\frac{2^{n-2}}{(2^j, 2^{n-2})}=\frac{2^{n-2}}{(k, 2^{n-2})}.$$