Compute the inverse of an integer modulo 100000000003

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 although hopefully different enough to still be of interest.

Answer 1

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.

Answer 2

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!

Answer 3

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.

Answer 4

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
-3 bytes thanks to isaacg
-1 byte thanks to Ørjan Johansen
-2 bytes thanks to Federico Poloni

x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x

Try it Online!

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 5

JavaScript (ES6), 153 143 141 bytes

Inspired by this answer from math.stackexchange.com.

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 6

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 7

Mathematica, 49 bytes

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&

Answer 8

PHP, 71 bytes

for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;

Testcases

Answer 9

Ruby, 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!