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. 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? 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. 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. 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. 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. 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.