# 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? Jul 4, 2017 at 10:31
• @immibis That looks fine.
– user9206
Jul 4, 2017 at 11:03
• What's special about 100000000003? (just wondering) Jul 4, 2017 at 21:19
• @Lembik In that case, could you mention that requirement that y<100000000003 in the question? Jul 4, 2017 at 21:25
• @NoOneIsHere It is the first twelve-digit prime number? 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
Jul 4, 2017 at 7:56
• I am guessing it's too late for me to tighten up the test cases....
– user9206
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. 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. 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

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!