# Set theory: Problem 4

### Solution

Proof: Let a, r, and m be integers, with m is positive. Suppose that $$a \equiv r \pmod{m}$$ and that $$p \in L(a,m)$$.

Since $$a \equiv r \pmod{m},$$ we know that $$m \mid (a-r)$$ (definition of congruence). By definition of divides, there must be an integer k such that $$mk=a-r$$. This means that $$a=r+mk$$.

Since $$p \in L(a,m)$$, there must be integers x and y such that $$p=ax+my$$. Substituting $$r+mk$$ for a, we get that

$$\begin{eqnarray*} p &=& (r+mk)x + my\\ & = & rx + mkx + my\\ & = & r(x) + m(kx+y) \\ \end{eqnarray*}$$

Let $$y'=kx+y$$. $$y'$$ is an integer because k, x, and y are integers. So we have $$p = rx + my'$$, where x and $$y'$$ are integers. This matches the defining property of L(r,m). So $$p \in L(r,m)$$, which is what we needed to show..