# Can the extended euclidean algorithm be used to calculate a multiplicative inverse in this case?

$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?

• 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$. – Dietrich Burde Apr 23 '16 at 16:00
• It would be correct, if the Bézout's coefficient were exact. – Bernard Apr 23 '16 at 16:11

$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: