[Math] Chinese Remainder Theorem for prime powers

chinese remainder theoremnumber theory

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

Best 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.

Related Question