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