# Given $N$ with $d$ prime factors. Can the number of unique values $x^d \mod N$ calculated for $d>2$? Does the total amount decrease at some point?

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)

Examples:
$$d=2$$
$$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$$

$$d=3$$
$$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$$

$$d=4$$
$$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$$

$$d=5$$
$$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$$

$$d=6$$
$$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. 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.
• 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? Commented Mar 20, 2022 at 14:35
• 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) Commented Mar 20, 2022 at 15:57
• $(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. Commented Mar 23, 2022 at 7:16