0
$\begingroup$

$e = 503456131$ is a prime number. It is relatively prime to the number $b = 10000123400257488$

If I use the extended euclidean algorithm (using this python implementation) to calculate the coefficients on the linear combination of e and b that gives 1, I obtain $-906226286492069\cdot e + 45623955 \cdot b = 1$.

Is it not correct that the coefficient on e, namely $-906226286492069$, is a multiplicative inverse of e (mod b)?

I thought this was correct, but $-906226286492069\cdot e$ divided by b gives remainder $10000096$.

What am I not seeing here?

$\endgroup$
  • $\begingroup$ No, $e=503456131$ is not a prime number. It is divisible by $23$. And take modulo $b$, i.e., divide $-906226286492069 e-1$ by $b$. $\endgroup$ – Dietrich Burde Apr 23 '16 at 16:00
  • $\begingroup$ It would be correct, if the Bézout's coefficient were exact. $\endgroup$ – Bernard Apr 23 '16 at 16:11
0
$\begingroup$

$e$ is not prime, but it is relatively prime to $b$. I think your last calculation is wrong, I tried it on WolframAlpha and got 1 back:

http://www.wolframalpha.com/input/?i=%E2%88%92906226286492069*503456131+mod+10000123400257488

$\endgroup$
  • $\begingroup$ Yes, I redid the calculations and my calculation was wrong. Apologies to everyone's time. $\endgroup$ – evianpring Apr 23 '16 at 17:04

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.