Solutions of non-linear congruence equation

Question

I am trying to find the number of solution to

$$ x^a(\mod b) =c:0\leq x\leq l$$

where $b\leq50$ but $a$ and $l$ can be large. My approach is to iterate through each value of $x$ from $0$ till $\min(b,l)$, and if it satisfies the equation add $ceil(\frac{l-x}b)$ (to account for the number of values of $x$ is are greater than $b$ but are equivalent in multiplicative field of $b$) to the number of solutions. I am not sure about the correctness of my algorithm. And can I extend my approach to to more than one variable like if there is

$$(x^a + y^a) (\mod b)=c$$

I can produce all unordered pairs of x and y such that $x\leq y$ till $(x,y)\leq \min(b,l)$ and again calculate $i=ceil(\frac{l-x}b)$ and $j=ceil(\frac{l-y}b)$ and multiply add the sum as :

$$t=\{i+i(i-1)\times2\text{ if }x=y , i\times j\times2\text{ if }x!=y \}$$

and take summation of t. I want to know if my algorithm is correct and if there is any other more efficient algorithm.

Answer 1

Several remarks:

1. Since you start iterating at $0$ you can (and should) stop at $b-1$, or $\min (b-1, l)$ to stay close to what you said.

2. It is not completely clear to me what you do when you mention the ceil as you say you add this to account for the values greater than $b$. The ceil you give is the total number of solutions you have corresponding to the one solution you found (but perhaps you meant this anyway).

3. Since you say that also $a$ can be large, you might want to exploit an additional way of saving iterations. For $x$ relatively prime to $b$ it is known that $x^{\varphi(b)}= 1 \pmod{b}$ where $\varphi$ denotes Euler's totient function (you could even use Carmichael's function instead, but this might not be worth the effort). So you can proceed regarding the exponent $a$ in the same as for the base $x$, but for the exponent calculate $\pmod{\varphi(b)}$ not modulo $b$. Yet note this works for $x$ coprime to $b$ only. But also for $x$ not coprime to $b$ the sequence $x^i$ is eventually periodic, so this would still work in principle.

4. Finally, do you know anything about the $c$. For example, if $c$ is coprime to $b$ you would know right away you can restrict to $x$ coprime. Conversely if it is not you can also restrict $x$ to not coprime and even more could be said.

And, yes, for more than one variable you could proceed like this, but for the case of equality I am a bit unsure why you ge the expression you get, I'd expect just $i^2$.

Regarding better alogorithms I am not sure, it also might depend on some things you did not make precise.