View Single Post
2007-12-03, 18:03   #2
jasonp
Tribal Bullet

Oct 2004

1101110011102 Posts

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.