[Question]
  [
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 < 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| < 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](https://codegolf.stackexchange.com/questions/215/compute-modular-inverse?rq=1) although hopefully different enough to still be of interest.
  
[Answer]
# Pyth, 24 bytes
```
L-b*/bJ+3^T11Jy*uy^GT11Q
```
[Test suite](https://pyth.herokuapp.com/?code=L-b%2a%2FbJ%2B3%5ET11Jy%2auy%5EGT11Q&test_suite=1&test_suite_input=2%0A3%0A1000000%0A50000000002&debug=0)
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.
[Answer]
# [Haskell](https://www.haskell.org/), 118 113 105 101 bytes
Inspired from [this solution](https://codegolf.stackexchange.com/a/129721/31975).
*-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!](https://tio.run/##HclLDoIwFAXQOau4gw5ahITWmfHJClwBonkNTSRAbVpiGLD3@jnT8@Q0uXnOOZBu7lofjsUES1KG2qjWKgtdRGy01cP4xoZQhkK6byTw7oga4l2fDclfO5jWiihSmZSYOa2CT10UXKb9NQxwfV549CAsHK4PyJtHfUGIo18hfYUJXil0ptLNX58/ "Haskell – Try It Online")
# [Haskell](https://www.haskell.org/), 48 bytes
A rewrite of [this solution](https://codegolf.stackexchange.com/a/129731/31975). 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!](https://tio.run/##NclBCsIwEEbhq/zLiU0gU3GZ3sATWGsDCgbToTSj5PbpovhWH7x3LJ9Xzq0V1PAVTZlGdYM6nZ/pN9dTDcEb6oj9xNydjeFjtCUmQcAS1@sDNArcgHVLoiCxKBBjcOvtxf/rLR@4tx0 "Haskell – Try It Online")
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 22 bytes
```
∧10^₁₁+₃;İ≜N&;.×-₁~×N∧
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r//1HHckODuEdNjUCk/aip2frIhkedc/zUrPUOT9cFitUdnu4HVPP/v9H/KAA "Brachylog – 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.
[Answer]
# Python, ~~53~~ ~~51~~ ~~49~~ ~~58~~ ~~53~~ 49 bytes
-2 bytes thanks to orlp  
-2 bytes thanks to officialaimm  
-4 bytes thanks to Felipe Nardi Batist  
```
x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x
```
[Try it Online!](https://tio.run/##K6gsycjPM/r/v8I2M6@gtERDk6vE1pCrPCMzJ1WhRLdEv0KrwqpE29ZY29BAS8vQkKugKDOvRAEo/v@/oQEIQCkA)
It took me ~30 minutes to figure this one out. My solution is to start with the first number that will mod to 1. This number is 1. If its divisible by x, then y is that number divided by x. If not, add 10000000003 to this number to find the second number which mod 1000000003 will equal 1 and repeat.
[Answer]
## JavaScript (ES6), ~~153~~ ~~143~~ 141 bytes
Inspired by [this answer from math.stackexchange.com](https://math.stackexchange.com/a/67199).
A recursive function based on the Euclidean algorithm.
```
f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)
```
Modulo is implemented by computing:
```
quotient = Math.floor(a / b);
remainder = a - b * quotient;
```
Because the quotient is also needed, doing it that way does actually make some sense.
### Test cases
```
let f =
f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)
console.log(f(2))
console.log(f(50000000002))
console.log(f(1000000))
```
[Answer]
# C++11 (GCC/Clang, Linux), ~~104~~ 102 bytes
```
using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}
```
<https://ideone.com/gp41rW>
Ungolfed, based on Euler's theorem and binary exponentation.
```
using T=__int128_t;
T m=1e11+3;
T f(T a,T r=1,T n=m-2){
    if(n){
        if(n & 1){
            return f(a * a - a * a / m * m, r * a - r * a / m * m, n / 2);
        }
        return f(a * a - a * a / m * m, r, n / 2);
    }
    return r;
}
```
[Answer]
# Mathematica, 49 bytes
```
x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&
```
[Answer]
# PHP, 71 bytes
```
for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;
```
[Testcases](http://sandbox.onlinephpfunctions.com/code/9e543565d82bcc273c4e6ae6ded5a91db9e290fd)
[Answer]
# [Ruby](https://www.ruby-lang.org/), 58 bytes
Uses isaacg's application of Fermat's little theorem for now while I finish timing the brute-force solution.
```
->n,x=10**11+3{i=n;11.times{i**=10;i-=i/x*x};i*=n;i-i/x*x}
```
Current brute force version, which is 47 bytes but ~~might be~~ *is* too slow:
```
->n,x=10**11+3{(1..x).find{|i|i*=n;i-i/x*x==1}}
```
[Try it online!](https://tio.run/##KypNqvyfZhvzX9cuT6fC1tBAS8vQUNu4OtM2z9rQUK8kMze1uDpTSwsoY52pa5upX6FVUWudqQWUztSF8P4XKKRFp6eWFOuV5Mdnxv43NAADQwA "Ruby – Try It Online")
]