The task is the following. Given an integer
x (such that
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.
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.
This is similar to this question although hopefully different enough to still be of interest.