Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.$
share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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).

EDIT added content

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

share|improve this answer
    
Once one solution is known how do I find the others? –  Andrew Tomazos Jul 29 '12 at 8:57
    
@user: I've added more. Does that answer your question? –  mixedmath Jul 29 '12 at 19:49
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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