Skip to main content

Section 9.1 Arithmetic modulo \(m\)

Definition 9.1.1.

For \(m\in \mathbb{N}\) and \(a,b\in \mathbb{Z}\text{,}\) we write \(a = b\mod m\) or sometimes \(a = b\mod m\) (read \(a\) is congruent to \(b\) modulo \(m\)) if one of the following equivalent conditions holds:

  • \(m\) divides \(a-b\text{;}\)

  • \(a\) and \(b\) have same remainder when divided by \(m\text{;}\)

  • \(b=qm+a\) for some \(q\in \mathbb{Z}\text{.}\)

Exercise.

\(32=2\mod 10\text{.}\) \(82=1 \mod 3\text{.}\)

  1. Since \(m\) divides \(a-a=0\text{,}\) we have that \(a = a\text{.}\)

  2. If \(a = b\mod m\text{,}\) then \(m\) divides \((a-b)\text{,}\) so \(m\) divides \((b-a)\) as well, hence \(b = a \mod m\text{.}\)

  3. Suppose \(a = b \mod m\) and \(b = c\mod m\text{.}\) Then \(m\) divides \(a-b\text{,}\) so \(a-b=km\) for some integer \(k\text{.}\) Moreover, \(m\) divides \(b-c\text{,}\) so \(b-c=jm\) for some integer \(j\text{.}\) Thus,

    \begin{equation*} a-c = a-b+b-c = km+jm = (k+j)m\text{,} \end{equation*}

    hence \(m\) divides \((a-c)\text{,}\) thus \(a = c \mod m\text{.}\)\qedhere

We have that \(m\) divides \(a-x\) and \(m\) divides \(b-y\)

  1. It is clear that \(m\) divides \(-(a-x)=(-a)-(-x)\text{,}\) so that \(-a = -x \mod m\text{.}\)

  2. The Linear Combination Lemma implies that \(m\) divides

    \begin{equation*} (a-x)+(b-y)=(a+b)-(x+y)\text{,} \end{equation*}

    and so \(a+b = x-y\mod m\text{.}\)

  3. \(a = x \mod m\) implies \(a=x+pm\) for some \(p\in\mathbb{Z}\) and \(b = y \mod m\) implies \(b=y+qm\) for some \(q\in\mathbb{Z}\text{.}\) Thus,

    \begin{equation*} ab = (x+pm)(y+qm) = xy+pmy+xqm+ pqm^2 = xy + m(py+xq+pqm)\text{,} \end{equation*}

    and so \(ab = xy\) by Definition 9.1.1(3).

  4. This can be proven by induction. For the base case of \(k=1\text{,}\) this is immediate. Now suppose \(a^{k} = x^{k}\mod m\) for some \(k\geq 1\text{.}\) Then by part (b) of this theorem with \(b=a^{k}\) and \(x=y^{k}\) and our induction hypothesis

    \begin{equation*} a^{k+1}=a\cdot a^{k} = a x^{k} \mod m \end{equation*}

    and then applying part (b) again but with \(b=y=x^k\text{,}\)

    \begin{equation*} a x^{k} = x\cdot x^k=x^{k+1}\text{.} \end{equation*}

    This proves the induction and hence the theorem. \qedhere

This result proves that many of the algebraic manipulations we enjoy performing on integers — addition, subtraction, and multiplication — can be done modulo \(m\) systematically. This simplifies many challenging-looking problems. Let's revisit our earlier example: is \(30^{99}+61^{100}\) divisible by 31? Note that \(30=31-1=-1\mod 31\) and \(61=2\cdot 31-1=-1\mod 31\text{,}\) and so

\begin{equation*} 30^{99}+61^{100} = (-1)^{99}+(-1)^{100}=-1+1=0 \mod 31\text{.} \end{equation*}

Indeed, \(31\) divides \(30^{99}+61^{100}\text{.}\)

Theorem 9.1.5 says we can add and multiply modulo \(m\text{.}\) Can we also divide? That is, if \(ad = bd\mod m\text{,}\) do we also have \(a = b\mod m\text{?}\) This is not always the case. Perhaps the simplest example is the following: \(2 = 0 \mod 2\text{,}\) but we cannot divide this equation by \(2\text{,}\) because \(1 \neq 0 \mod 2\text{.}\) More subtly, \(12 = 24 \mod 6\text{,}\) but here we cannot divide by \(3\text{,}\) because \(4 \neq 8 \mod 6\text{.}\) The following theorem says when we can divide in this way.

Suppose \(a\) and \(m\) are coprime and \(xa = ya\mod m\text{.}\) Then \(m\) divides \(xa-ya=(x-y)a\text{.}\) Since \(m\) and \(a\) are coprime, \(m\) divides \(x-y\text{,}\) and so \(x = y\mod m\) by definition. The second part of the proposition follows from the first.

Find an integer \(x\in \{0,1,..,6\}\) so that \(4^{6} = x\mod 7\text{.}\)

Let's look at some powers of \(4\) and see what they are modulo \(7\text{.}\)

\begin{align*} 4^2 \amp = 16 =14+2 = 2 \mod 7\\ 4^4 \amp = (4^2)^2 = 2^2 =4 \mod 7\text{.} \end{align*}

Thus,

\begin{equation*} 4^6=4^2\cdot 4^4 = 2\cdot 4=8 = 1 \mod 7\text{.} \end{equation*}

This is certainly much quicker than computing \(4^6\) by hand and then doing long division!