Closed form for $(a \cdot x)\bmod n = r$

Question

Given $a$, $n$ and $r$, is there a closed form for computing $x$?

$(a \cdot x)\bmod n = r$

$x$ in [0..n)

For example,

$(7 \cdot x)\bmod 10 = 1$

$x = 3, 13, 23,...$

$x = 3$ for $x$ in $[0..n)$

I rewrote the equation but not sure how to proceed:

$ x = \frac {qn + r}{a}$

Answer 1

Not a closed formula, but an algorithm to find a solution, if there is one. Assume $a, n$ are not both zero, otherwise this is trivial.

You are looking for $x, y$ such that $$ a x + n y = r. $$ A necessary condition for this to happen is that $$\tag{cond} \gcd(a, n) \mid r $$ Conversely, if (cond) holds, use the extended Euclidean algorithm to find $u, v$ such that $$ a u + b v = \gcd(a, n), $$ and then multiply by the integer $\dfrac{r}{\gcd(a, n)}$ to get $$ a \left(u\cdot \dfrac{r}{\gcd(a, n)}\right) + b \left(v\cdot \dfrac{r}{\gcd(a, n)}\right) = r, $$ so that $$ x = u \cdot \dfrac{r}{\gcd(a, n)} $$ is a solution. To find all the solutions, note that two solutions differ by a $t$ such that $a y \equiv 0 \pmod{n}$.

Answer 2

Closed form for $ax\equiv r\mod n$ with $gcd(a,n)=1$ is

$x\equiv a^{-1}r\mod n$.

The condition $gcd(a,n)=1$ is sufficient and necessary that $a$ is invertible modulo $n$.