# Solve mod equation, how?

Ok so how would I solve for $j$: $(e*j)\bmod z=1$ When $e$ and $z$ are known integers. I am at a loss with this without using trial and improvement. Is there a formula I could use?

• Sorry, I'm not sure I understand the edit. – user3537381 Jan 5 '15 at 12:38
• What is modular about your question? What is the difference between the $*$ operator and juxtaposition; is the latter something else than multiplication? – Marc van Leeuwen Jan 5 '15 at 12:38
• I had to add a tag, since the question involves 'mod', I just assumed it related to said tag, it seems I was incorrect. Sorry, I am no mathematician. – user3537381 Jan 5 '15 at 12:40
• My bad; there was % in the original question, but it was not there when I looked. There is the mathematical equivalent $\bmod$ now. – Marc van Leeuwen Jan 5 '15 at 12:42
• Modular inverses are usually computed using the extended Euclidean algorithm. – fkraiem Jan 5 '15 at 12:43

## 1 Answer

You are asking for a modular inverse $j$ of $e$ modulo $z$. It only exists if $\gcd(e,z)=1$, in which case it is a unique class modulo $z$. You can find that class using Bézout coefficients: there exist $s,t\in\Bbb Z$ such that $se+tz=\gcd(e,z)$, and if the latter is $1$ then $j=s$ is a solution of the problem.

• I'm confused, so the value of gcd(e,z) is known, where does t come in? – user3537381 Jan 5 '15 at 12:52
• Sorry, I said "is" in place of "if" (corrected now). Since $e,z$ are known, you can compute their $\gcd$. Unless the result is$~1$, there will be no solution at all. If it is$~1$, you can find a solution using the Bézout coefficients (which you can find while computing $\gcd(e,z)$). – Marc van Leeuwen Jan 5 '15 at 13:42
• So in this instance, how would you use the Bézout coefficients to solve the equation? – user3537381 Jan 5 '15 at 16:23
• As I said, if $s,t$ are Bézout coefficients, then $j=s$ is a solution. – Marc van Leeuwen Jan 5 '15 at 16:41