number of solution to nonlinear congruence equation

Question

I am trying to find the number of solution to

       x^a (mod b) =c with 0<=x<=u

where b<=50 but a and u can be large. My approach is to iterate through each value of x from 0 till min(b,u), and if it satisfies the equation add ceil((u-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<=y till (x,y)<=min(b,u) and again calculate i=ceil((u-x)/b) and j=ceil((u-y)/b) and multiply add the sum as :

            t={i+i*(i-1)*2 if x=y , i*j*2 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

Yes if x^a mod b = c then (x+b)^a mod b = c. So there would be a total of 1 + floor((u-x)/b) solutions thus far. You just have to remember to skip those numbers while you are searching for other solutions from (x+1) to min(u,b).

The concept works for 2 variables but much more computationally intensive. You solve x^a mod b = d and save the count as T[d] where 0 ≤ d < b. You might ask why 0 ≤ d < b and not 0 ≤ d ≤ c. This example is why: if c=7 and b=35 then (x,y) such that x^a mod 35 = 8 and y^a mod 35 = -1 ≡ 34 would be a solution as well.

Then the total number of solutions is similar to what you suggested except I don't bother with separate handling of x=y and x≠y:

for (i=0 ; i < b ; i++)
   count += T[i]*T[(b +c -i)%b];