# Chinese Remainder Theorem for prime powers

Let's say I want to find some $x$ that leaves a remainder of $a_1$ when divided by prime power $p^{k_1}$, and a remainder of $a_2$ when divided by $p^{k_2}$, and a remainder of $a_3$ when divided by $p^{k_3}$, and so on, for some fixed prime $p$.

I was trying to understand the answer in this post but didn't understand how you could solve a congruence system with a bunch of moduli that were basically all prime powers of the same prime, as these are, by definition, not coprime (which I assumed was necessary for the Chinese Remainder Theorem to even work in the first place).

• You can’t in general. The system $x \equiv 1 \bmod 2$, but $x \equiv 0 \bmod 2^k$ for some $k > 1$ is impossible to solve for $x$. I didn’t read the linked question & answer, though. Jan 7 '15 at 18:14

## 1 Answer

As the comments suggest, this is not always possible. It requires $a_i \equiv a_j \mod p^{k_j}$ for all $k_i > k_j$. If that holds, then all you really have to satisfy is $x \equiv a_l \mod p^{k_l}$ where $k_l$ is the max.

• There's no solution to $x \equiv 8 \mod 27$ and $x \equiv 1 \mod 9$ since $8 \not\equiv 1 \mod 9$. Jan 7 '15 at 18:29
• You'd need something like: $x \equiv 1 \mod 3$, $x \equiv 7 \mod 9$, $x \equiv 16 \mod 27$. The first two are implied by the third. Jan 7 '15 at 18:35
• If $x \equiv 16 \mod 27$ then there is an integer $k$ such that $x=16+27k$. Then $x = 1+3(5+9k)$. Since $5+9k$ is an integer, $x \equiv 1 \mod 3$. Jan 8 '15 at 19:15