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.

  • 3
    $\begingroup$ 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$. $\endgroup$ Aug 20 '20 at 2:20
  • $\begingroup$ @ArturoMagidin that's a neat observation. Any idea what happens in the case that the exponent is a power of $2$? $\endgroup$
    – Favst
    Aug 20 '20 at 2:47
  • 1
    $\begingroup$ 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$). $\endgroup$ Aug 20 '20 at 3:43
  • 1
    $\begingroup$ Yes; these are all well-known facts. $\endgroup$ Aug 20 '20 at 14:35
  • 2
    $\begingroup$ @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. $\endgroup$
    – Favst
    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}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.