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, 2015 at 18:14

1 Answer 1

Reset to default
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, 2015 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, 2015 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, 2015 at 19:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .