Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have integers $a, b$, and $p$ where $p$ is prime. We also have naturals $n$ and $m$, where $n < m$.

Prove that the system of linear congruences:

$$x \equiv a \pmod{p^n}$$

$$x \equiv b \pmod{p^m}$$

has a solution if and only if

$$a \equiv b \pmod{p^n}$$

I've tried saying:

$$x - a \mid p^{n}$$

$$x - b \mid p^{m}$$

$$p^{n} \mid p^{m}$$

$$\Rightarrow x - a \mid p^{m}$$

Then I can get:

$$[x]_{p^{m}}- [a]_{p^{m}} = [0]_{p^{m}}$$

$$[x]_{p^{m}}- [b]_{p^{m}} = [0]_{p^{m}}$$

$$\Rightarrow [x]_{p^{m}}- [a]_{p^{m}} = [x]_{p^{m}}- [b]_{p^{m}}$$

$$[a]_{p^{m}} = [b]_{p^{m}}$$

but that doesn't seem to be what I want to show. I need to show

$$[a]_{p^{n}} = [b]_{p^{n}}$$

but I can't see how.

share|cite|improve this question
up vote 2 down vote accepted

The sentence $x\equiv a\pmod{p^n}$ is true precisely if $p^n$ divides $x-a$. Similarly, $x\equiv b\pmod{p^m}$ if and only if $p^m$ divides $x-b$. Since $n\lt m$, if both congruences hold, then $p^n$ divides both $x-a$ and $x-b$. It thus divides their difference.

I will temporarily leave the other direction to you.

share|cite|improve this answer
I see where I went wrong now. p$^{n}$ divides $x-a$ and I had it the other way around. I see now how to finish the proof. Thank you. – mottese Feb 27 '13 at 5:37

More generally, a system \begin{cases} x \equiv a \pmod{u}\\ x \equiv b \pmod{v} \end{cases} will have a solution if and only if $$a \equiv b \pmod{\gcd(u, v)}.\tag{1}$$

If the system has a solution $x$, then $$a + u s = x = b + v t\tag{2}$$ for some $s, t$, so $$b - a = u s - v t\tag{3}$$ which yields (1).

Conversely, if (1) holds, then write $\gcd(u, v) = u y - v z$ for some $y, z$, and multiply by the integer $(b-a)/\gcd(u, v)$ to get (3) and thus the solution $x$ of (2).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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