Valer BOCAN’s Web Log

As I was working to implement the scalable distribution system I envisioned here, I needed a way to find the solution of a system of linear congruencies in the form of the Chinese Remainder Theorem.

Theory

Given a set of simultaneous congruencies

X ≡ Ai (mod mi)

for I = 1,…, r and for which the mi are pairwise relatively prime, the solution of the set of congruencies is

X = A1 * B1 * M / m1 + … + Ar * Br * M / mr (mod M)

where M = m1 * m2 * … * mr

and the bi terms are determined from bi * M / mi ≡ 1 (mod mi).

For instance, the set of congruencies:

X ≡ 3 (mod 27)

X ≡ 4 (mod 13)

X ≡ 2 (mod 11)

has the solution X = 2136.

C# Implementation

This is a screenshot of the code that solves the system equation above:

Here is the C# code for finding the solution of the Chinese Remainder Theorem. The code I wrote in C# also uses the code I published in a previous blog post.

This entry was posted on Sunday, October 14th, 2007 at 5:20 pm and is filed under Misc. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.