# Proving solutions exist in a system of linear congruences

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.

-

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.

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

-