Chinese Remainder Theorem

The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in polynomial time. Shortest code wins.

For example, say we're given these constraints (% represents mod):

n % 7  == 2
n % 5  == 4
n % 11 == 0

One solution is n=44. The first constraint is satisfied because 44 = 6*7 + 2, and so 44 has remainder 2 when divided by 7, and thus 44 % 7 == 2. The other two constraints are met as well. There exist other solutions, such as n=814 and n=-341.

Input

A non-empty list of pairs (p_i,a_i), where each modulus p_i is a distinct prime and each target a_i is a natural number in the range 0 <= a_i < p_i. You can take input in whatever form is convenient; it doesn't have to actually be a list of pairs. You may not assume the input is sorted.

Output

An integer n such that n % p_i == a_i for each index i. It doesn't have to be the smallest such value, and may be negative.

Polynomial time restriction

To prevent cheap solutions that just try n=0, n=1, n=2, and so on, your code must run in polynomial time in the length of the input. Note that a number m in the input has length Θ(log m), so m itself is not polynomial in its length. This means that you can't count up to m or do an operation m times, but you can compute arithmetic operations on the values.

You may not use an inefficient input format like unary to get around this.

Other bans

Built-ins to do the following are not allowed: Implement the Chinese Remainder theorem, solve equations, or factor numbers.

You may use built-ins to find mods and do modular addition, subtraction, multiplication, and exponentiation (with natural-number exponent). You may not use other built-in modular operations, including modular inverse, division, and order-finding.

Test cases

These give the smallest non-negative solution. Your answer may be different. It's probably better if you check directly that your output satisfies each constraint.

[(5, 3)]
3

[(7, 2), (5, 4), (11, 0)]
44

[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
1770977011

[(982451653, 778102454), (452930477, 133039003)]
68121500720666070
• Why no division? – jimmy23013 Mar 22 '15 at 8:31
• @user23013 No modular division, since it's basically modular inverse. – xnor Mar 22 '15 at 8:34
• Does matrix inversion count as solving equations? – flawr Mar 22 '15 at 15:44
• @flawr: I would think so. – Alex A. Mar 22 '15 at 19:32
• @xnor: What do you think? And how about optimization functions? – flawr Mar 22 '15 at 20:49

Mathematica, 5551 45

Modular inverse is banned, but modular exponentiation is allowed. By Fermat's little theorem, n^(-1) % p == n^(p-2) % p.

Example:

In:= f = (PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&;

In:= f[{{5, 3}}]

Out= 3

In:= f[{{7, 2}, {5, 4}, {11, 0}}]

Out= 1584

In:= f[{{5, 1}, {73, 4}, {59, 30}, {701, 53}, {139, 112}}]

Out= 142360350966

Just for fun:

• You can save one byte by swapping the order of the arguments of the innermost function, such that you can use PowerMod[#2,#-2,#] and I also don't think there's a requirement for the function to be named, bringing it down to 48. – Martin Ender Mar 22 '15 at 15:46
• Yes, unnamed functions are OK. – xnor Mar 22 '15 at 23:29

Python 2, 1651019998 85 bytes

Using Fermat's little theorem like the other answers. Doesn't bother with keeping final sum within modular range, since we're not interested in the smallest solution. Thanks Volatility for saving 13 bytes.

l=input();x=reduce(lambda a,b:a*b,l,1)
print sum(x/a*b*pow(x/a,a-2,a)for a,b in l)

[(5, 3)]
3
[(7, 2), (5, 4), (11, 0)]
1584
[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
142360350966
• You can remove the space before for. – isaacg Mar 22 '15 at 6:24
• x/a*b*pow(x/a,a-2,a)for a,b in l should work. – Volatility Mar 23 '15 at 6:05
• Excellent point! I was trying to get rid of the obvious redundancy there but forgot that I could just unpack. – Uri Zarfaty Mar 23 '15 at 8:18

Pyth, 403736 29

M*G.^G-H2Hsm*edg/u*GhHQ1hdhdQ

Uses Fermat's little theorem, thanks to alephalpha. Computes using this formula.

Ruby, 129

Well, comrades, it seems Ruby solutions must be longer because modular exponentiation is not available without loading openssl library and doing conversions to OpenSSL::BN. Still, had fun writing it:

require("openssl")
z=eval(gets)
x=1
z.map{|a,b|x*=a}
s=0
z.map{|a,b|e=a.to_bn;s+=(x/a).to_bn.mod_exp(e-2,e).to_i*b*x/a}
puts(s)
• You don't need the parens when calling require, eval, or puts. – Tutleman Jul 27 '17 at 15:30

Python 2, 61

n=P=1
for p,a in input():n+=P*(a-n)*pow(P,p-2,p);P*=p
print n

This employs a variation of the product construction that other answers use.

The idea is to loop over the constraints and update the solution n to meet the current constraint without messing up the prior ones. To do so, we track the product P of the primes seen up to now, and observe that adding a multiple of P has no effect modulo any already-seen prime.

So, we just need to change n to satisfy n%p == a by adding the right multiple of P. We solve for the coefficient c:

(n + P*c) % p == a

This requires that c = (a-n) * P^(-1), where the inverse is taken modulo p. As others note, the inverse can be computed by Fermat's Little Theorem as P^(-1) = pow(P,p-2,p). So, c = (a-n) * pow(P,p-2,p), and we update n by n+= P * (a-n) * pow(P,p-2,p).

Haskell, 68 100 bytes

f l=sum[p#(m-2)*n*p|(m,n)<-l,let a#0=1;a#n=(a#div n 2)^2*a^mod n 2modm;p=product(map fst l)divm]

Usage: f [(5,1), (73,4), (59,30), (701,53), (139,112)] -> 142360350966.

Edit: now with a fast "power/mod" function. Old version (68 bytes) with inbuilt power function:

f l=sum[l#m^(m-2)modm*n*l#m|(m,n)<-l]
l#m=product(map fst l)divm
• I suspect your implementation of power-mod is not polynomial-time since the exponent produces a huge number before the mod. Have you tried the last test case? – xnor Mar 22 '15 at 22:49
• @xnor: the last test case runs out of memory after a few seconds on my 2GB machine. I've added a fast power/mod function. – nimi Mar 23 '15 at 20:23