Given a number $N$ with $d$ unique prime factors. Can the number of unique values $v$ with $$v \equiv x^d \mod N$$ $$x\in[0,N-1]$$ $$N = \prod_{i=1}^{d} p_i$$ be calculated for $d>2$? (Q1)
Does the total amount decrease at some point? (Q2)

For simplification we assume each prime factor $p_i > 5$.
Or for target use case each $p_i$ is big enough to avoid easy factorization.

Solving trial:
For $d=1$ it's trivial. If we insert every value from $0$ to $N-1$ for $x$ in $x^1 \mod N$. There we always have $N$ unique values.
So $N_{x^1} = N$

For $d=2$ we have two interacting groups from $p_1$ and $p_2$ with size $p_1-1$ and $p_2-1$ with a shared prime factor of at least $2$. If we combine them we get (in most cases) a group size of
$$L = \mathrm{lcm}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$ And a number of $L_n$ instances $$L_n = \mathrm{gcd}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$ And some special cases for $0$, $1$, numbers with the '$\frac{p_i-1}{2}$'-th power ($\mod N$) and some special special case if the base is also $p_i^2$
With this we can calculate the total number of quadratic residue ($d=2$) $N_{x^2}$ among $\mathbb Z/N\mathbb Z$: $$N_{x^2} = L_n\cdot L + 2 + 2 (\frac{p_1-1}{2}-1)+2(\frac{p_2-1}{2}-1)+2$$ (more details in answer and question)

Q1: Is there a more general equation for $d>2$?

Testing around:
In some test for $d \in [2,3,4,5,6]$ I computed all possible values and noticed the ratio $$R_d = \frac{N_{x^d}}{N}$$ can be $1$ for $d\in [3,5]$ but also just $0.1$. For $d=2$ it's $R_2 \approx 0.25$.
$R_4$ was always $<0.05$ in test cases. $R_6$ seems to be even smaller with some $R_6<0.001$

Q2.1: Will this ratio continue to decrease for larger (even) $d$?

Q2.2: Does the total amount of $N_{x^d}$ decrease at some $d$?
Let's assume $N$ gets 512-bit bigger for each new prime factor, will there be a $d$ (with a $d \cdot 512$-bit $N$) which has less $N_{x^d}$ than $N_{x^2}$ (with $2\cdot 512 = 1024$-bit $N$)? (Q2.3)

$N = 50471 =41\cdot 1231$ with $N_{x^2}=12936$ and $R_2 = 0.256$
$ N = 28363 = 113 \cdot 251$ with $N_{x^2}= 7182 $ and $R_2 = 0.253$

$N =18031=13\cdot 19\cdot 73$ with $N_{x^3}=875$ and $R_3 =0.04$
$N =11339=17\cdot 23\cdot 29$ with $N_{x^3}=11339$ and $R_3 =1.0$

$N =97867=7\cdot 11\cdot 31\cdot 41$ with $N_{x^4}=4224$ and $R_4=0.04$
$N =63427=7\cdot 13\cdot 17\cdot 41$ with $N_{x^4}=880$ and $R_4=0.01$

$N =3453307=11\cdot 13\cdot 19\cdot 31\cdot 41$ with $N_{x^5}=46683$ and $R_5=0.0135$
$N =1659931=7\cdot 13\cdot 17\cdot 29\cdot 37$ with $N_{x^5}=1659931$ and $R_5=1.0$

$N=28709681=7\cdot 11\cdot 13\cdot 23\cdot 29\cdot 43$ with $N_{x^6}=51840$ and $R_6=0.0018$
$N=35797223=7\cdot 11\cdot 17\cdot 23\cdot 29\cdot 41$ with $N_{x^6}=408240$ and $R_6=0.011$
$N=28527037=7\cdot 11\cdot 17\cdot 19\cdot 31\cdot 37$ with $N_{x^6}=18109$ and $R_6=0.000635$


1 Answer 1

  1. Yes, for square free $N$ the formula is $$\prod_{i=1}^d\left(1+\frac{p_i-1}{(d,p_i-1)}\right)$$

  2. The above expression will equal $N$ iff $(d,p_i-1)=1$ for all $i$. For odd $d$ we can find arbitrarily many primes with this property. It follows that the supremum of $R_d$ is 1, for odd $d$ which includes large values of $d$

Conversely, for any given $d$ we can construct $N$ from primes all of which are 1 mod $d$. In such a way we can find $N$ such that $R_d(N)=O(d^{-d})$, but such $N$ are sparse.

  • $\begingroup$ interesting, I thought it's a more complicated equation. Thanks for answering again. Just one note: is $(a,b)$ a common short term for $\mathrm{gcd}(a,b)$ or did you just omit them for any reason? $\endgroup$
    – J. Doe
    Commented Mar 20, 2022 at 14:35
  • $\begingroup$ so related to Q2.2. If $N$ increases by about $B$ bit with each factor we would also need such many unique prime factors ($2^B$) to decrease the total count which is impossible (not that many primes) $\endgroup$
    – J. Doe
    Commented Mar 20, 2022 at 15:57
  • 1
    $\begingroup$ $(a,b)$ for the greatest common divisor is common notation in number theory, though the more explicit $\mathrm{gcd}(a,b)$ is often used in cryptography. I think that unless $d$ is very large or $B$ is very small, there should still be plenty of primes. $\endgroup$
    – Daniel S
    Commented Mar 23, 2022 at 7:16

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.