1
$\begingroup$

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?$$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.