Thread: CRT optimisation? View Single Post
 2016-03-30, 10:20 #10 Nick     Dec 2012 The Netherlands 110100010012 Posts May I suggest that the modern algebraic way of looking at this offers some advantages here? If we are working with integers modulo 5, for example, then we regard integers a and b as equivalent if (and only if) 5 divides a-b, so we have 5 equivalence classes: {...,-15,-10,-5, 0,5,10,15,...} {...,-14,-9,-4, 1,6,11,16,...} {...,-13,-8,-3, 2,7,12,17,...} {...,-12,-7,-2, 3,8,13,18,...} {...,-11,-6,-1, 4,9,14,19,...} For any integer a, we write $$\bar{a}$$ to denote the equivalence class of a, i.e. the entire set of all integers equivalent to a modulo 5 (this is the set in the above list which a appears in). We then define addition and multiplication on these sets by: $\begin{eqnarray*} \bar{a}+\bar{b} & = & \overline{a+b} \\ \bar{a}\cdot\bar{b} & = & \overline{a\cdot b} \end{eqnarray*}$ for any integers a & b, and show that this is well-defined (i.e. the definition does not depend on the representative elements chosen). Thus, for example, we can write $$\bar{4}^2=\overline{-1}^2=\bar{1}$$. Viewed this way, we are not tempted to write something like "30 mod 5 mod 7" because 30 mod 5 is then the set $$\overline{30}=\bar{0}$$ and not all elements of the set have the same remainder on division by 7, so the final "mod 7" is not a valid operation.