# 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 < 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.

• So a-(a/b)*b is fine? Commented Jul 4, 2017 at 10:31
• @immibis That looks fine.
– user9206
Commented Jul 4, 2017 at 11:03
• What's special about 100000000003? (just wondering) Commented Jul 4, 2017 at 21:19
• @Lembik In that case, could you mention that requirement that y<100000000003 in the question? Commented Jul 4, 2017 at 21:25
• @NoOneIsHere It is the first twelve-digit prime number? Commented Jul 4, 2017 at 22:19

# 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.

• Very nice indeed!
– user9206
Commented Jul 4, 2017 at 7:56
• I am guessing it's too late for me to tighten up the test cases....
– user9206
Commented Jul 4, 2017 at 9:45
• @Lembik I'd do it anyways, but opinions may vary. It's your challenge, make it work the way you want it to. Commented Jul 4, 2017 at 9:56
• The way the question is written, it is possible you could drop the final reduction, although I asked for a clarification whether a result <100000000003 is required. Commented Jul 4, 2017 at 17:59

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-tdivx*x==0)(+(10^11+3))1divx  Try it online! • Awesome! I like the exponentiation by squaring approach. Commented Jul 4, 2017 at 8:02 • The shortest solution would be something like Try it online! but I don't think its performance is acceptable ... Commented Jul 4, 2017 at 8:05 • (1) It's shorter to make g an operator (e?b)a s|... (2) If you switch a and s then you can make ! a non-operator and inline y into it. (3) You can get rid of the expensive where by a last trick, at the cost of duplicating z. Try it online! Commented Jul 4, 2017 at 9:02 • Now those are nice tricks! Commented Jul 4, 2017 at 9:30 • Oh, and |e==0=a gets rid of that pesky duplication. Commented Jul 4, 2017 at 9:43 # 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. • Wow, I never would have expected constraint arithmetic to pull that off. Awesome! Commented Jul 4, 2017 at 8:21 • @isaacg The speed of this is unfortunately completely dependent on the value of İ, so this is still pretty slow for big products. Commented Jul 4, 2017 at 8:23 • Updated the question. Does your code always take less than 30 minutes? – user9206 Commented Jul 4, 2017 at 9:59 # Python, 5351495853 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. • The first number that will mod to 1 is 1... – orlp Commented Jul 4, 2017 at 9:07 • @orlp lol thanks. That saved me 2 bytes :) Commented Jul 4, 2017 at 9:08 • Interesting, on TIO this is fast for all the test cases but a bit random keyboard banging gave me 421385994 which times out. Commented Jul 4, 2017 at 9:10 • @ØrjanJohansen Good sleuthing. – user9206 Commented Jul 4, 2017 at 9:11 • If you need b only once, why not hardcoding it? Commented Jul 4, 2017 at 18:07 ## JavaScript (ES6), 153143 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)) • You only need 64 bit flooring in the last occurence so you can replace the other ones with 0|x/y and remove the declaration – Oki Commented Jul 4, 2017 at 11:19 # 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; }  • ISO C++ only requires long to be at least 32-bit, so it can't necessarily hold 1e11 + 3. It's 32-bit on x86-64 Windows. long is a 64-bit type on x86-64 Linux (and other OSes that use the SystemV ABI), though. So to be fully portable, you'd need to use long long, which is guaranteed to be at least 64-bit since C++11. Commented Jul 4, 2017 at 18:21 • __int128_t doesn't seem to be standard C++, it seems to be a gcc extension, it would be cool if you'd state this as a language (C++11 + gcc). Commented Jul 4, 2017 at 18:38 • This is not supposed to be a C++ experts site, I hoped no one will notice. Commented Jul 4, 2017 at 18:47 • @PeterCordes Code golf doesn't need to be portable or even well-formed, it just needs to work on one implementation. Commented Jul 4, 2017 at 22:25 • @aschepler: I know, which is why I said "you would need". I thought it was useful to point out which platform it would/wouldn't work on, in case anyone tried it and ran into trouble. Commented Jul 5, 2017 at 5:50 # Mathematica, 49 bytes x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&  • How long does this take to run? – user9206 Commented Jul 5, 2017 at 6:52 • Less than 0.001s on my computer (for case 2^40-1) Commented Jul 11, 2017 at 8:37 # PHP, 71 bytes for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo\$o;


Testcases

# 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!