Garner's algorithm (source code)

= Garner's algorithm
{c}

= Garner algorithm
{c}
{synonym}

= Garner
{c}
{synonym}

<Garner's algorithm> solves a system $x\equiv a_i\pmod{m_i}$ for pairwise coprime moduli by constructing a mixed-radix expansion
$$
x=c_0+c_1m_0+c_2m_0m_1+\cdots,\qquad0\leq c_i<m_i.
$$
After fixing earlier digits, let $P_i=\prod_{j<i}m_j$ and $s_i=\sum_{j<i}c_jP_j$. The next digit is $c_i\equiv(a_i-s_i)P_i^{-1}\pmod{m_i}$. Coprimality ensures that the <modular inverse> exists.

For $x\equiv2\pmod3$, $x\equiv3\pmod5$, $c_0=2$ and $c_1\equiv(3-2)3^{-1}\equiv2\pmod5$, giving $x=8$ modulo fifteen. The mixed-radix form constructs the <Chinese remainder theorem> solution incrementally.