Thus we see that we actually only have 18 encodings.

Next let's set about calculating a CRT residues class representative, or

more informally, converting a sequence of CRT residues to the corresponding integer.

So we have an unknown value of x and known values of R1 and

R2 as well as known values of M1 and M2 that are co-prime.

Since we are in a mod in world, the best we can do is recover one of the values

in the same congruence class as the actual value of x.

Naturally, we'll opt for the class representative.

The overall modulus is, therefore, the produce of M1 and M2.

So how can we find x?

We'll start off by setting up a linear equation in which each individual

residue is multiplied by some coefficient And the products are then summed together.

This results in an equation in which each term contains the information about

exactly one of the residues, and

therefore each term corresponds to exactly one of our CRT moduli.

Since we are looking for

the least residue, we need to reduce the sum by our overall modulus in.

In general we have k moduli and hence one term for each corresponding residue.

The overall modulus is the product of the k individual moduli.

Now our task is to find suitable coefficients.

The key in this quest is to make sure that our equation

reduces to the proper residues for each modulus.

After all, any integer that reduces to this sequence of residues is,

by definition, in that CRT residue's equivalence class, and

since we have reduced this integer by the overall modulus we know that it is

the least residue, or class representative, of that equivalence class.

We can guarantee this outcome,

as long as each of the coefficients satisfy two constraints.

First, each term that does not contain the residue for

a given modulus must vanish when reduced by that modulus.

This requires that each coefficient be congruent to zero for

every modulus Except the one corresponding to the residue it contains.

Second, the term that does contain the residue for

a given modulus is must reduce suggest that residue when reduced by that modulus.

This requires that each coefficient be congruent to 1 for

the modulus corresponding to the residue it contains.