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.

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

2 Answers

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|improve this answer
add comment

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