# Is there a known formula for the number of $k^{\text{th}}$ power residues modulo $2^n$?

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.

Given $$n$$ and $$k,$$ if there are general formulas for when the coprime condition on $$a$$ is lifted, which Stangl also solves in the quadratic case, that would be interesting too, but perhaps that is the subject matter for another question. A variant of CRT again boils this down to the prime power case.

• The structure of $(\mathbb{Z}/2^n\mathbb{Z})^*$ is well understood: it is isomorphic to $C_2\times C_{2^{n-2}}$ (when $n\geq 2$), For $k$ odd, the $k$th power map is a bijection so all $2^{n-1}$ possible values of $a$ modulo $2^n$ are $k$th power residues. So you only need to worry about $k=2^j$. Aug 20 '20 at 2:20
• @ArturoMagidin that's a neat observation. Any idea what happens in the case that the exponent is a power of $2$? Aug 20 '20 at 2:47
• Clealry, if $j\geq n-1$, then only $1$ is a $2^j$th power modulo $2^n$. For $1\leq j\lt n-1$, the subgroup the image is generated by $5^{2^j}$, and has order $2^{n-1-j}$, so there are exactly $2^{n-1-j}$ residues that are $2^j$th power residues. (Every unit modulo $2^n$ is of the form $\pm 5^k$ for some $k$). Aug 20 '20 at 3:43
• Yes; these are all well-known facts. Aug 20 '20 at 14:35
• @ArturoMagidin I checked out the revised formula with the powermod(a,b,c) function on WolframAlpha and it works out. In any case, I appreciate the key ideas that you mentioned which allowed me to write up a proof. Aug 21 '20 at 15:37

Here is the full proof based on ArturoMagidin's comments on the original post (this proof appears in a book that I am writing). 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\}$$. Letting $$\nu_2 (k)=j,$$ we will show that $$|S_k (2^n)| = \begin{cases} 2^{n-j-2} &\text{ if } 0\le j\le n-3\\ 1 &\text{ if } j\ge n-2 \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-2}.$$ 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})}.$$ For $$j\ge n-2$$ this is equal to $$\frac{2^{n-2}}{2^{n-2}} = 1,$$ and for $$j\le n-3$$ this is equal to $$\frac{2^{n-2}}{2^j}=2^{n-j-2}.$$