View Single Post
Old 2007-12-03, 18:03   #2
Tribal Bullet
jasonp's Avatar
Oct 2004

1101110011102 Posts

Originally Posted by drido View Post
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.
jasonp is offline   Reply With Quote