Find all the possible $a,b$ in $a * b \equiv c \pmod{x}$

Question

$$a * b \equiv c \pmod{x}$$

Where $a,b,c,x \in \mathbb{Z}$ and $0 < a \leq b < x; 0 < c < x$

What is the most efficient way to find all the possible $a,b$?

Answer 1

Note for any $a$ which $\gcd(x,a)=d$ we can solve $a*k \equiv d*m$ for any multiple of $d$ but we can never solve an $a*k \equiv N$ if $d\not \mid N$.

So consider all $a$ so that $\gcd(a,x)|c$. And solve. And not if if $ab \equiv c=c'\gcd(a,x)$ then $a(b+\frac {x}{\gcd(a,x)})\equiv ab + \frac a{\gcd(a,x)}x \equiv ab \equiv c$ as well.

So for example to solve $ab = 52\pmod {810}$. $810 = 2*3^4*5$ but $52=4*13$. so if $a$ is a multiple of $3$ of $5$ solutions will be impossible but all $a$ that aren't are solvable.

So $a = 1$ and $b = 52$.

$a=2$ and $b=26$ but $\gcd(2,810)=2$ so $a=26; b= 26+410$ is solution.

skip $a=3$

$a=4$ and as $26\not \mid 4$ and $810$ to make it divisible by $4$. $b = \frac {810+26}4=209$ as well as $b=209+410$

Next is $a=7$ and use Euclid's algorithm to solve.

and so on.

Answer 2

I used Euler's totient function to calculate the number of the expected solutions in $O(N)$ where $N=x$

Then I tested each possible combination of $a,b$ in $O(N^2)$.