Quote:
Originally Posted by drido
i need to solve a linear system modulo a composite number.
if this number is n = p*q where p and q are prime, i know i have to
solve the system modulo p and modulo q and combine the solutions
with the chinese remainder theorem.
but what if this number is a power of a prime (n = p^k) or a composition
of powers (n = p1^k1 * p2^k2) ?
|
Use Hensel's lemma; an answer mod p uniquely specifies an answer mod p^k, if the latter exists. Repeat for each p^k then use the CRT as before. The presence of powers in the CRT modulus doesn't matter (CRT only cares that the p^k are coprime to each other), though it requires finding inverses mod p^k which also needs Hensel's lemma.