Compute the inverse of an integer modulo 100000000003

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.

Haskell, 118 113 105 101 bytes

Inspired from this solution.

-12 from Ørjan Johansen

p=10^11+3
k b=((p-2)?b)b 1
r x=x-div x p*p
(e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e]

Try it online!

Haskell, 48 bytes

A rewrite of this solution. While fast enough for the test vector, this solution is too slow for other inputs.

s x=until(\t->t-t`div`x*x==0)(+(10^11+3))1`div`x

Try it online!

Brachylog, 22 bytes

∧10^₁₁+₃;İ≜N&;.×-₁~×N∧

Try it online!

This took about 10 minutes for 1000000 with a slightly different (and longer) version of the code which was exactly two times faster (checked only positive values of İ instead of both positive and negatives). Therefore this should take about 20 minutes to complete for that input.

Explanation

We simply describe that Input × Output - 1 = 100000000003 × an integer, and let constraint arithmetic find Output for us.

∧10^₁₁+₃                   100000000003
        ;İ≜N               N = [100000000003, an integer (0, then 1, then -1, then 2, etc.)]
            &;.×           Input × Output…
                -₁         … - 1…
                  ~×N∧     … = the product of the elements of N

We technically do not need the explicit labeling ≜, however if we do not use it, ~× will not check the case N = [100000000003,1] (because it's often useless), meaning that this will be very slow for input 2 for example because it will need to find the second smallest integer instead of the first.