# Finding an integer that satisfies a congruence class equation

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?

-

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