0:00

In this lesson on the Chinese remainder theorem,

Â we'll explore the restrictions that exist on the choice of moduli available to us.

Â We'll also learn how to convert from a CRT representation to the integer or

Â more precisely the class representative that it corresponds to.

Â That will prepare us for the next lesson where we will examine some,

Â though certainly not all, of the things that CRT is well suited for and

Â also some of the things that it isn't.

Â Again, certainly not all.

Â 0:28

In the prior lesson we didn't place any restrictions on the choice of our moduli

Â and so you might have found yourself wondering if, given arbitrary choices for

Â the CRT moduli, whether all CRT residues are actually possible.

Â Certainly, there is nothing that prevents us from writing down

Â any CRT residue we want.

Â But it is only useful if it corresponds to some subset of the integers.

Â So let's consider what would happen if we chose as our moduli 6 and 9.

Â This would seem to indicate that we can represent up to 54 different integers.

Â Or 54 equivalence classes.

Â But are we guaranteed none of these classes are empty?

Â That each class actually contains integers.

Â We have this guarantee provided but knowing one of the residues

Â places no restrictions on what any of the others can be.

Â Now might be a good time to pause the video and see if you can decide whether we

Â can uniquely represent the integers 0 through 53 as CRT residues

Â using 6 and 9 as our moduli and if not, why not?

Â And also how many non empty CRT equivalence classes are there?

Â 1:37

So let's say that we choose x such that x mod 6 is 0.

Â This means that we know that the number is divisible by 6 which means that it is

Â also divisible by three.

Â But any number that is divisible by three can only have a mod 9 residue of 0,

Â 3, or 6.

Â None of the others are possible.

Â So, for example, the equivalence class corresponding to the CRT encoding

Â 0,1 is empty because it is not possible for an integer

Â to have a mod 6 residue of 0 and also a mod 9 residue of 1.

Â The residues of an integer using two different moduli are independent

Â only if the two moduli are relatively prime, that they share no common factors.

Â Thus the set of moduli that we use in any CRT representation must be pairwise

Â co-prime, meaning that none of them share a common factor with any of the others.

Â Going back to our choice of 6 and 9, these share a common factor of 3.

Â We can keep the 3 in one of the moduli, but

Â we must divide it completely out of all of the others.

Â The only way to do this gives us 2 and 9, since the only other choices would be

Â 6 and 1 or 1 and 18, both of which are just normal modular worlds.

Â Although, that does show that a normal modular world is a CRT world,

Â just one that is pretty boring as it only has one meaningful modulus.

Â 3:04

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.

Â 5:27

So let's set about making this happen.

Â We know that any term that is a multiple of a modulus

Â is concurrent to 0 when reduced by that modulus.

Â Now consider that N, our overall modulus, is the product of all of the moduli.

Â Hence, if we divide N by a given modulus,

Â what we have is a value that is the product of all the other moduli.

Â And therefore is congruent to 0 when reduced by

Â any of the other moduli except the one we divided by.

Â We can satisfy our first requirement by exploiting this fact.

Â Multiplying each terminar linear equation by the appropriate factor therefore

Â guarantees that when we reduce the equation by the various moduli

Â that each CRT moduli is a function of exactly one term and

Â that it is the term that contains the correct residue.

Â But since it may not be the correct value, we still have another factor,

Â A prime, that we need to determine for each coefficient.

Â So the final value of Ai is the product of A prime and

Â our ratio of the overall modulus to that term's CRT modulus.

Â Even without knowing what A prime is, we know that Ai is congruent to 0 for

Â all of the moduli other than Mi.

Â But we have no basis for believing that Ai is congruent to 1 when

Â we reduced mod Mi but that's a pretty easy error to fix.

Â 6:49

To satisfy the second requirement,

Â we exploit the fact that the product of any integer and

Â its modular inverse is congruent to one when reduced by that modulus.

Â But this requires that the modular inverse actually exist which, in turn,

Â requires that our integer be relatively prime to Mi.

Â However, we have that covered,

Â since our integer is the overall modulus divided by the current CRT modulus.

Â Since each CRT modulus is relatively prime to all of the other CRT moduli,

Â it is also relatively prime to the product of all of them.

Â In fact, this is why the moduli must be pairwise co-prime.

Â If they aren't, we then have some coefficients that won't exist.

Â Our final expression for our coefficients is simply the product of the overall

Â modulus divided by that term's CRT modulus.

Â Then multiplied by the multiplicative inverse of that ratio in that

Â term's CRT modulus' world.

Â We can then reduce this by the overall modulus, though this isn't essential,

Â since we will do this again after evaluating the entire

Â linear equation for x.

Â We already know that Ai is congruent to 0 for all of the other moduli, but

Â you should now be confident that it also congruent to 1 for that term's moduli.

Â 8:06

We can now summarize the central relations associated with

Â the Chinese Remainder Theorem quite succinctly.

Â Going forward, our modulus is the product of k relatively primed CRT moduli and

Â our C representation of x is a sequence of residues, one for each CRT modulus.

Â To go from the CRT residues back to x, or at least its class representative, we

Â evaluate a linear equation, and reduce it mod N, in which each of the coefficients

Â in our linear equation is found according to the process we just developed.

Â Let's apply what we've learned, and found the class representative for

Â the CRT value (2, 7, 19) in a (mod (4, 9, 25)) world.

Â First, we need to find the overall modulus

Â which we just multiply the three moduli and we get 900.

Â Next we need to find each coefficient.

Â For the modulus of 4, we divide 900 by 4 to get 225.

Â Next we find the mod for inverse of 225,

Â which turns out to be 1, since 221 itself is congruent to 1 in a mod 4 world.

Â Next we get our final coefficient for the first CRT modulus by multiplying 225 and

Â one to get 225.

Â And reduce it mod 900 which leaves us with 225.

Â Finding the coefficient for the modulus of 9 is very similar and

Â I recommend that you pause here and see what you get before continuing.

Â The second coefficient associated with the modulus of 9 is 100.

Â While the final coefficient corresponding to the modulus 25 is 576.

Â That gives us our final general equation for a mod 4925 world and

Â when we evaluate it for our particular residues, 2, 7 and 19, we get 394.

Â A quick check confirms that 394 does indeed belong in the 2,

Â 7, 9 residue class.

Â I recommend that you play around with CRT transforms a bit before going on to

Â the next lesson, in which we explore some of the things that we can and

Â can't do with the Chinese remainder theorem.

Â