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:
- \$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