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

Question

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

Answer 1

$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