Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We have integers $a = 1231940$, $b = 9935$ and $n = 3999831$ and the ring $\mathbb{Z}/n\mathbb{Z}$. Now we should find an integer $x$ that satisfies the equation $[a] \odot_n [x] = [b]$. How can such an equation be solved?

share|cite|improve this question
up vote 1 down vote accepted

This is the same question as solving the congruence $ax\equiv n\pmod b$. There is a general algorithm for this problem.

  1. It is a necessary condition that $\gcd(a,n)$ divides $b$ (otherwise there are no solutions). We compute that $\gcd(a,n) = 1987$, and indeed $b=1987\cdot 5$.
  2. We divide everything in sight by that greatest common divisor, yielding the equivalent congruence $620x\equiv 5\pmod{2013}$.
  3. Now the coefficient of $x$ is relatively prime to the modulus. Using the extended Euclidean algorithm, we compute the modular inverse $620^{-1}\equiv 1763\pmod{2013}$.
  4. Finally, we multiply both sides of the congruence $620x\equiv 5\pmod{2013}$ by this modular inverse, yielding $x\equiv 763\pmod{2013}$. Any integer $x$ satisfying this congruence does the trick (and these are all the solutions).
share|cite|improve this answer

Note that $a$ is a multiple of $b$, namely $a=124\cdot b$. Write $c:=124$. Since $\gcd(c,n)=1$, you can use the extended euclidean algorithm to find that $$\underset{=: x}{\underbrace{1838632}}\cdot c - 57\cdot n = 1$$ In other words, $[x]\odot_n[c]=[1]$, in your notation. Now this means $$[x]\odot_n[a] = [x]\odot_n[c]\odot_n[b] = [1]\odot_n[b] = [b].$$

share|cite|improve this answer

Your Answer


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.