Chinese Remainder Theorem Algorithm

The Chinese remainder theorem algorithm reconstructs an unknown integer from its remainders when divided by several pairwise coprime numbers, computing the unique remainder that integer leaves when divided by the product of those numbers. It works by using Bezout's identity, the fact that pairwise coprime integers can always be combined into a linear combination equal to one, to build weighted combinations of the given divisors that isolate each individual remainder's contribution to the final answer. Its earliest known statement is a specific numerical puzzle in the fifth-century Chinese text Sunzi Suanjing, asking for a number that leaves remainder two when divided by three, three when divided by five, and two when divided by seven, though that text posed the problem without giving a general method for solving it. The general solving procedure was developed further over the following centuries by Indian and Islamic mathematicians before Carl Friedrich Gauss gave it its modern treatment using modular arithmetic notation in his 1801 Disquisitiones Arithmeticae. Today the algorithm underlies techniques ranging from calendar calculations to fast modular arithmetic used in cryptographic computation.