[Question]
  [
The [Chinese Remainder Theorem](http://en.wikipedia.org/wiki/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:
* \$n \equiv 2 \mod 7\$
* \$n \equiv 4 \mod 5\$
* \$n \equiv 0 \mod 11\$
One solution is \$n=44\$. The first constraint is satisfied because \$44 = 6\times7 + 2\$, and so \$44\$ has remainder \$2\$ when divided by \$7\$, and thus \$44 \equiv 2 \mod 7\$. 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 \le 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 \equiv a\_i \mod p\_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, 1, 2, \dots\$, 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
```
  
[Answer]
# Mathematica, ~~55~~ ~~51~~ 45
Modular inverse is banned, but modular exponentiation is allowed. By Fermat's little theorem, `n^(-1) % p == n^(p-2) % p`.
```
(PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&
```
Example:
```
In[1]:= f = (PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&;
In[2]:= f[{{5, 3}}]
Out[2]= 3
In[3]:= f[{{7, 2}, {5, 4}, {11, 0}}]
Out[3]= 1584
In[4]:= f[{{5, 1}, {73, 4}, {59, 30}, {701, 53}, {139, 112}}]
Out[4]= 142360350966
```
---
Just for fun:
```
ChineseRemainder@@Reverse@Thread@#&
```
[Answer]
## Python 2, ~~165~~ ~~101~~ ~~99~~ ~~98~~ 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[0],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
```
[Answer]
# Pyth, 40 37 36 29
```
M*G.^G-H2Hsm*edg/u*GhHQ1hdhdQ
```
Uses Fermat's little theorem, thanks to alephalpha. Computes using [this formula](http://en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case).
[Answer]
**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)
```
[Answer]
# 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](http://en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case) 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)`.
[Answer]
# 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 2`mod`m;p=product(map fst l)`div`m]
```
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)`mod`m*n*l#m|(m,n)<-l]
l#m=product(map fst l)`div`m
```
]