Set theory: Problem 4


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