1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – k.stm
    Jan 7 '15 at 18:14
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ There's no solution to $x \equiv 8 \mod 27$ and $x \equiv 1 \mod 9$ since $ 8 \not\equiv 1 \mod 9$. $\endgroup$
    – Aeryk
    Jan 7 '15 at 18:29
  • $\begingroup$ 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. $\endgroup$
    – Aeryk
    Jan 7 '15 at 18:35
  • $\begingroup$ 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$. $\endgroup$
    – Aeryk
    Jan 8 '15 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.