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


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.

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

9 Answers 9


Pyth, 24 bytes


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.

  • \$\begingroup\$ Very nice indeed! \$\endgroup\$
    – user9206
    Jul 4, 2017 at 7:56
  • \$\begingroup\$ I am guessing it's too late for me to tighten up the test cases.... \$\endgroup\$
    – user9206
    Jul 4, 2017 at 9:45
  • 1
    \$\begingroup\$ @Lembik I'd do it anyways, but opinions may vary. It's your challenge, make it work the way you want it to. \$\endgroup\$
    – isaacg
    Jul 4, 2017 at 9:56
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 4, 2017 at 17:59

Haskell, 118 113 105 101 bytes

Inspired from this solution.

-12 from Ørjan Johansen

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!

  • \$\begingroup\$ Awesome! I like the exponentiation by squaring approach. \$\endgroup\$
    – isaacg
    Jul 4, 2017 at 8:02
  • \$\begingroup\$ The shortest solution would be something like Try it online! but I don't think its performance is acceptable ... \$\endgroup\$
    – bartavelle
    Jul 4, 2017 at 8:05
  • \$\begingroup\$ (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! \$\endgroup\$ Jul 4, 2017 at 9:02
  • \$\begingroup\$ Now those are nice tricks! \$\endgroup\$
    – bartavelle
    Jul 4, 2017 at 9:30
  • \$\begingroup\$ Oh, and |e==0=a gets rid of that pesky duplication. \$\endgroup\$ Jul 4, 2017 at 9:43

Brachylog, 22 bytes


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.


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.

  • 1
    \$\begingroup\$ Wow, I never would have expected constraint arithmetic to pull that off. Awesome! \$\endgroup\$
    – isaacg
    Jul 4, 2017 at 8:21
  • 1
    \$\begingroup\$ @isaacg The speed of this is unfortunately completely dependent on the value of İ, so this is still pretty slow for big products. \$\endgroup\$
    – Fatalize
    Jul 4, 2017 at 8:23
  • \$\begingroup\$ Updated the question. Does your code always take less than 30 minutes? \$\endgroup\$
    – user9206
    Jul 4, 2017 at 9:59

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

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.

  • \$\begingroup\$ The first number that will mod to 1 is 1... \$\endgroup\$
    – orlp
    Jul 4, 2017 at 9:07
  • \$\begingroup\$ @orlp lol thanks. That saved me 2 bytes :) \$\endgroup\$ Jul 4, 2017 at 9:08
  • \$\begingroup\$ Interesting, on TIO this is fast for all the test cases but a bit random keyboard banging gave me 421385994 which times out. \$\endgroup\$ Jul 4, 2017 at 9:10
  • \$\begingroup\$ @ØrjanJohansen Good sleuthing. \$\endgroup\$
    – user9206
    Jul 4, 2017 at 9:11
  • 1
    \$\begingroup\$ If you need b only once, why not hardcoding it? \$\endgroup\$ Jul 4, 2017 at 18:07

JavaScript (ES6), 153 143 141 bytes

Inspired by this answer from math.stackexchange.com.

A recursive function based on the Euclidean algorithm.


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 =



  • \$\begingroup\$ 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 \$\endgroup\$
    – Oki
    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;}


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 & 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;
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 4, 2017 at 18:21
  • \$\begingroup\$ __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). \$\endgroup\$ Jul 4, 2017 at 18:38
  • 3
    \$\begingroup\$ This is not supposed to be a C++ experts site, I hoped no one will notice. \$\endgroup\$
    – SteelRaven
    Jul 4, 2017 at 18:47
  • \$\begingroup\$ @PeterCordes Code golf doesn't need to be portable or even well-formed, it just needs to work on one implementation. \$\endgroup\$
    – aschepler
    Jul 4, 2017 at 22:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Jul 5, 2017 at 5:50

Mathematica, 49 bytes

  • \$\begingroup\$ How long does this take to run? \$\endgroup\$
    – user9206
    Jul 5, 2017 at 6:52
  • \$\begingroup\$ Less than 0.001s on my computer (for case 2^40-1) \$\endgroup\$
    – Keyu Gan
    Jul 11, 2017 at 8:37

PHP, 71 bytes




Ruby, 58 bytes

Uses isaacg's application of Fermat's little theorem for now while I finish timing the brute-force solution.


Current brute force version, which is 47 bytes but might be is too slow:


Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.