The usual Chinese Remainder Theorem requires that the moduli be pairwise relatively prime. A modification states that a given system of linear congruences $x\equiv a_i\pmod{m_i}$ is solvable if and only if $a_i\equiv a_j\mod{(n_i,n_j)}$ for all $i\neq j$.

I've looked around and I've got it narrowed down to this:

The system consisting of the congruences $x\equiv a\pmod{p}$ and $x\equiv b\pmod{p^2}$ is solvable if and only if $a\equiv b\pmod{p}$.

What I can't seem to find is how $a\equiv b\pmod{p}\Rightarrow$ a solution exists.


1 Answer 1


If $a\equiv b\pmod{p}$, then $x=b$ is a solution :-)

More generally, if we're given a prime number $p$ and integers $a$ and $b$ with $a\equiv b\pmod{p}$, the solutions to the system $$\begin{align} x&\equiv a\pmod{p}\\ x&\equiv b\pmod{p^2} \end{align}$$ are precisely $$x\in\{b+kp^2\mid k\in\mathbb{Z}\}.$$

  • $\begingroup$ :-) Thanks, it was hiding in plain sight! $\endgroup$
    – ttt
    Aug 11, 2013 at 15:09

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.