Compute the inverse of an integer modulo 100000000003 The task is the following. Given  an integer x (such that x modulo 100000000003 is not equal to 0) presented to your code in any way you find convenient, output another integer y &lt; 100000000003 so that (x * y) mod 100000000003 = 1. 

You code must take less than 30 minutes to run on a standard desktop machine for any input x such that |x| &lt; 2^40.

Test cases

Input: 400000001. Output: 65991902837

Input: 4000000001. Output: 68181818185

Input: 2. Output: 50000000002

Input: 50000000002. Output: 2.

Input: 1000000. Output: 33333300001

Restrictions 

You may not use any libraries or builtin functions that perform modulo arithmetic (or this inverse operation).  This means you can't even do a % b without implementing % yourself. You can use all other non-modulo arithmetic builtin functions however.

Similar question

This is similar to this question although hopefully different enough to still be of interest.
Pyth, 24 bytes

L-b*/bJ+3^T11Jy*uy^GT11Q


Test suite

This uses the fact that a^(p-2) mod p = a^-1 mod p.

First, I manually reimplement modulus, for the specific case of mod 100000000003. I use the formula a mod b = a - (a/b)*b, where / is floored division. I generate the modulus with 10^11 + 3, using the code +3^T11, then save it in J, then use this and the above formula to calculate b mod 100000000003 with -b*/bJ+3^T11J. This function is defined as y with L.

Next, I start with the input, then take it to the tenth power and reduce mod 100000000003, and repeat this 11 times. y^GT is the code executed in each step, and uy^GT11Q runs it 11 times starting with the input.

Now I have Q^(10^11) mod 10^11 + 3, and I want Q^(10^11 + 1) mod 10^11 + 3, so I multiply by the input with *, reduce it mod 100000000003 with y one last time, and output.