Search code examples
mathematical-optimization

Splitting an unsigned mod operation into parts


Is there a way to split a mod operation on unsigned integers into easier ones?

For example, x % 28. Is there a way to split it into operations with 4 and 7?


Solution

  • If you want to work with values x % 4 and x % 7 instead of solely with x % 28, you can do that as they are equivalent representations of x (you don't lose data/info and do not make extra assumptions).

    This is basically the inverse of the Chinese Remainder Theorem / problem, where you are given the moduli x % m_i (such as x % 4 and x % 7), knowing that they are coprime, you compute x % M where M = m_1 * ... *m_k (here x % 28 where M = 4*7 = 28), the product of the moduli. The theorem states that the mapping between the two representations is bijective, all x % mod M classes will have a unique "solution" in the x % m_1, x % m_2, ... modulo system, and vica versa. Therefore, yes you can this just as if you were using only X % M, just make sure that the moduli you use are pairwise coprime.

    In your case, you take M, the easiest way to get pairwise coprime moduli is if you write it in its prime factor decomposition form: M = p_1a_1 * p_2a_2 * ..., and choose m_i = p_ia_i. Then just compute the remainders.

    If you want to represent x % 28 as an equation of x % 4 and x % 7 like in Eric Postpischil's comment, you can also do that, the coefficients can be constructed based on this (note that my notation of M is N on the page).