2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Sorry, I'm not sure I understand the edit. $\endgroup$ – user3537381 Jan 5 '15 at 12:38
  • $\begingroup$ What is modular about your question? What is the difference between the $*$ operator and juxtaposition; is the latter something else than multiplication? $\endgroup$ – Marc van Leeuwen Jan 5 '15 at 12:38
  • $\begingroup$ 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. $\endgroup$ – user3537381 Jan 5 '15 at 12:40
  • $\begingroup$ My bad; there was % in the original question, but it was not there when I looked. There is the mathematical equivalent $\bmod$ now. $\endgroup$ – Marc van Leeuwen Jan 5 '15 at 12:42
  • $\begingroup$ Modular inverses are usually computed using the extended Euclidean algorithm. $\endgroup$ – fkraiem Jan 5 '15 at 12:43
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm confused, so the value of gcd(e,z) is known, where does t come in? $\endgroup$ – user3537381 Jan 5 '15 at 12:52
  • $\begingroup$ 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)$). $\endgroup$ – Marc van Leeuwen Jan 5 '15 at 13:42
  • $\begingroup$ So in this instance, how would you use the Bézout coefficients to solve the equation? $\endgroup$ – user3537381 Jan 5 '15 at 16:23
  • $\begingroup$ As I said, if $s,t$ are Bézout coefficients, then $j=s$ is a solution. $\endgroup$ – Marc van Leeuwen Jan 5 '15 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.