1
$\begingroup$

Is there an explicit formula for the number of fourth powers mod n?

Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for higher powers.

[1] S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n

$\endgroup$
4
  • 4
    $\begingroup$ Reduce to the case $n$ is a prime power, then it's straightforward. $\endgroup$ Aug 5, 2011 at 18:50
  • 1
    $\begingroup$ @Geoff: Of course it's multiplicative by inspection (or the CRT, I suppose). $\endgroup$
    – Charles
    Aug 6, 2011 at 1:29
  • 1
    $\begingroup$ @Charles: Yes, by the CRT. Now add the fact that $\mathbb{Z}/n\mathbb{Z}$ has a simple structure when $n$ is a prime power (it is cyclic or the 2-element group times a cyclic group). $\endgroup$
    – GH from MO
    Aug 8, 2011 at 10:07
  • 1
    $\begingroup$ The number of distinct fourth powers modulo $n$ is tabulated at oeis.org/A052273 and the link bibliotekanauki.pl/articles/1390691 is given to Shuguang Li, On the number of elements with maximal order in the multiplicative group modulo $n$, Acta Arithmetica 1998;86(2):113–32 with particular reference to the proof of Theorem 2.1. $\endgroup$ Nov 7, 2022 at 1:53

1 Answer 1

3
$\begingroup$

As stated in the comments (1 2 3), the counting function is multiplicative, so only the prime power case needs to be addressed. Last year, I derived a somewhat concise formula for $\lvert R_k (p^m)\rvert$, where $R_k (p^m)$ is the set of $k$-th power residues (not necessarily coprime to the modulus) modulo $p^m$. It was recently accepted for publication: Counting general power residues. Here is the result, quoted from the paper:

Let $\epsilon$ be the parity function. So for integers $t$, $ \epsilon(t) = \begin{cases} 0 &\text{ if } 2\mid t\\ 1 &\text{ if } 2\nmid t. \end{cases} $

Let $p$ be a prime, and $k\ge 2$ and $m\ge 1$ be integers. Let $r$ be the remainder of $m$ upon division by $k$. Let \begin{align*} \alpha &= \dfrac{p-1}{(k,p-1)},\\ \beta &= (\nu_p (k)+1)(1-\epsilon(k))(1-\epsilon(p))+\nu_p(k)\epsilon (p),\\ \gamma &= \begin{cases} k &\text{ if } k \mid m\\ r &\text{ if } k\nmid m. \end{cases}. \end{align*} Then \begin{align*} \lvert R_k (p^m)\rvert &= \alpha \cdot \left(\dfrac{p^k}{p^{\beta +1}}\cdot \dfrac{p^m-p^{\gamma}}{p^k-1}+ \left\lceil\dfrac{p^{\gamma}}{p^{\beta+1}}\right\rceil\right)+1\\ &= \alpha \cdot \left\lceil\dfrac{1}{p^{\beta +1}}\cdot \dfrac{p^{m+k}-p^{\gamma}}{p^k-1}\right\rceil+1. \end{align*}

(Note that the $\dfrac{p^k}{p^{\beta +1}}\cdot \dfrac{p^m-p^{\gamma}}{p^k-1}$ term is necessarily an integer, so it can be absorbed into the ceiling term $\left\lceil\dfrac{p^{\gamma}}{p^{\beta+1}}\right\rceil$ as shown.)

Obviously the proof is what matters, but computational testing matched the results of the formulas in all cases tried.

References: My initial inspiration was a paper Counting squares in $\mathbb Z_n$ of Walter Stangl, who addressed the quadratic case. Also, my discussion with Arturo Magidin in Is there a known formula for the number of $k^{\text{th}}$ power residues modulo $2^n$? was helpful in the derivation. After submission to the first journal that I tried, a reviewer noted that similar formulas were mentioned by Maxim Korolev in On the average number of power residues modulo a composite number (DOI), who himself referred to a paper The Number of kth Power Residues Modulo m of Ji Chungang.

Note: Given the content of the above references, the originality of my minor contribution rests only on unifying the various cases by noticing their similarities, summing a series that the others left unclosed, and expanded elementary exposition. I am not surprised that I was able to publish it only after trying a couple of other more well-known journals first, but it was a little surprising that the arXiv rejected posting it.

$\endgroup$
4
  • 2
    $\begingroup$ Perhaps your formula, case $k=4$, should be recorded at oeis.org/A052273 $\endgroup$ Nov 7, 2022 at 1:56
  • $\begingroup$ Definitely looking forward to the paper! $\endgroup$
    – Charles
    Nov 7, 2022 at 2:17
  • $\begingroup$ @Charles here you go: doi.org/10.7546/nntdm.2022.28.4.730-743 $\endgroup$
    – Favst
    Nov 7, 2022 at 12:35
  • 2
    $\begingroup$ @GerryMyerson After a few days of collaborating with the OEIS editors, the updates have been posted: oeis.org/A052273 . Also, the OEIS page and its various crossref pages noted conjectures of Richard Mathar on the subject. I have managed to modify my formula to prove them all. I sent off the resolution of these predicted formulas to the arXiv (which once again put it on hold) and a journal. Thanks for linking me to the OEIS page. $\endgroup$
    – Favst
    Nov 16, 2022 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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