# Finding solutions to $n m\equiv x \mod n$

Given a modulus $n\in\mathbb{N}$ and another natural number $0<x<n$, what's an efficient algorithm to enumerate all pairs of natural numbers $(a,b)\in\mathbb{N}^2$ such that both $a$ and $b$ are less than $n$ and $$ab\equiv x \mod n\text?$$

• You might want to fix the title, since as written it's asking a different (and easier) question than the body of your post. – Rick Decker Nov 2 '17 at 19:33

## 1 Answer

Let's solve the problem for a specific $a$. Observe that $ab \equiv x \pmod{n}$ if and only if there exists a $m \in \mathbb{Z}$ such that

$\qquad ab + mn = x$

By the Bezout theorem, the above has solutions if and only if $x \mid (a, n)$ (the "if" arrow is the theorem, the "only if" arrow is trivial). One of those solutions can be found by the Extended Euclid algorithm, and all the others can be obtained observing that if $(b, m)$ is a solution, then

$\qquad \left( b + \frac{n}{(a, n)}, m + \frac{a}{(a, n)} \right)$

is also a solution. Repeating the above process for all $a \in \mathbb{Z}/n\mathbb{Z}$ yields all the pairs you are looking for. While it's rather naive, I don't think you can get much better than that if you're looking for all solutions.