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:

\$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 &lt; 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
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##&amp;@@#/#,#-2,#]x).#2&amp;@@Thread@#&amp;

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

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@#&amp;