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?
Asked
Active
Viewed 238 times
2
1 Answers
2
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.
Marc van Leeuwen
- 115,048
-
I'm confused, so the value of gcd(e,z) is known, where does t come in? – user3537381 Jan 05 '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 05 '15 at 13:42
-
So in this instance, how would you use the Bézout coefficients to solve the equation? – user3537381 Jan 05 '15 at 16:23
-
As I said, if $s,t$ are Bézout coefficients, then $j=s$ is a solution. – Marc van Leeuwen Jan 05 '15 at 16:41
%in the original question, but it was not there when I looked. There is the mathematical equivalent $\bmod$ now. – Marc van Leeuwen Jan 05 '15 at 12:42