# How many elements $a \in \Bbb{Z}_N$ such that $ax \equiv y \mod N$

Consider the ring $\Bbb{Z}_N$ of arithmetic modulo $N$: $\{0,1,2, \ldots ,N-1\}.$

Given $x,y \in \Bbb{Z}_N,$ how many of the elements of $\Bbb{Z}_N$ when multiplied with $x \pmod{N}$ result in $y$? And how can we calculate what they are efficiently?

The answer is a function of $N, x$ and $y.$

For example if $N = 10,$ $x = 6$ and $y = 2,$ then there are two elements $\{2,7\}$:

1. $2x = 12 \pmod{10} = 2 = y.$
2. $7x = 42 \pmod {10} = 2 = y.$
-

So we are asking how many $a$ are there such that, for a given $x,y$, we have $ax \equiv y \mod n$. This falls under the Linear Congruence Theorem, which states that there will be a solution only if $\gcd(x,n)|y$, and if there are any solutions, then there are exactly $\gcd(x,n)$ of them.

Further, it is very easy to find all solutions once one is known, and the Euclidean algorithm will quickly give one solution (if there is a solution).

In a comment, the OP asks Once one solution is known how do I find the others?

On the one hand, if you'd clicked on the wiki link answers this in the third sentence (the first restates the problem, the second gives the gcd requirement for a solution, and the third gives all the solutions). On the other, self-contained answers are usually simply better.

First one uses the Euclidean Algorithm to find a solution. In this case, it's often called the extended Euclidean Algorithm, as one uses it to find $\gcd(x,n)$, then 'extends it' to find integers $\alpha, \beta$ s.t. $\alpha x + \beta n = \gcd(x,n)$. If $\gcd(x,n)|y$, then in particular $y = c\gcd(x,n)$ for some $c$. But then $c\alpha x + c \beta n = y$, giving that $c\alpha x \equiv y \mod n$. So $c \alpha$, which I will now call $a_0$ is a solution: $a_0 x \equiv y \mod n$.

To get all the other solutions, one looks at $\left\{ a_0 + k \dfrac{n}{\gcd(x,n)} \right\}$ across $k \in \mathbb{Z}$. Let's check:

$\left(a_0 + \dfrac{kn}{\gcd(x,n)}\right)x = a_0x + \dfrac{kx}{\gcd(x,n)}n \equiv a_0x \equiv y \mod n$, where I used that $\gcd(x,n)|x$ to pull the $n$ aside. Going through, one sees that this gives $\gcd(x,n)$ different solutions $\mod n$.

-
Once one solution is known how do I find the others? – Andrew Tomazos Jul 29 '12 at 8:57
You want to find number of $k$ (mod $N$) for which $\exists m$ satisfying $kx+mN =y$. Now such $k$ exist iff $\gcd(x,N)$ divides $y$ and in that case there are exactly $\gcd(x,N)$ solutions modulo $N$.