algebraic structures, Blogs

Congruence Modulo n

Now that we’ve looked at equivalence relations, we extend this idea and begin to look at congruence relations. A congruence relation will be an equivalence relation which also respects the operation on the set we are looking. Therefore, we will follow a similar process to show a congruence relation as we did for an equivalence, but we will have another step.

Congruence Modulo \(n\)

Prove that congruence modulo \(n\) is a congruence relation on the set of integer with respect to addition and multiplication.

Video Explanation

In this video we show that congruence mod \(n\) is an equivalence relation.

In this video we show that congruence mod \(n\) respects addition and multiplication.

Definitions

Our goal is to show that the defined relation is indeed a congruence relation. In this case, the name, congruence modulo \(n\), seems to imply that we have a congruence. However, we cannot assume this directly and must show it as we will in this post. Therefore, we will start with recalling the definition of congruence modulo \(n\).

For more insight into this, we can look at the post Modular Arithmetic: 2+2=1!. However, we defined \(a \equiv b \text{ mod } n\) if, when divided by \(n\), the remainders of \(a\) and \(b\) are the same. To find the remainder, we could use The Division Algorithm. Instead of using this direct definition, we also noted that we have an equivalent definition given by
\begin{align*}
a \equiv b \text{ mod } n \text{ if } n |(b-a).
\end{align*}
That is, \(a\) and \(b\) are equivalent mod \(n\) if \(n\) divides the difference of \(b\) and \(a\). This definition will prove to be more useful in writing the proof.

Now that we have a working definition of congruence mod \(n\), we will now need to check each of properties of an equivalence relation as well as show that addition and multiplication are respected by the relation.

Equivalence Relation

We need to show that congruence modulo \(n\) is reflexive, symmetric and transitive.

Reflexive

Recall that a relation, \(\theta\), is reflexive on a set \(S\) if \(a \mathrel{\theta} a \) for all \(a \in S\). Therefore, we need to show that \(a \equiv a \text{ mod } n\) for all \(a, n \in \mathbb{Z}\). This is equivalent to showing \(n | (a-a)\). But, since \(a-a=0=n*0\) for all \(n \in \mathbb{Z}\) it is indeed the case that this relation is reflexive.

Symmetric

A relation, \(\theta\), is symmetric on \(S\) if \(a \mathrel{\theta} b\) implies \(b \mathrel{\theta} a\) for all \(a,b \in S\). That is, we now need to show that if \(a \equiv b \text{ mod } n\), then \(b \equiv a \text{ mod }n\). Using our definition, this means that we need to show that if \(n| b-a\), then \(n |a-b\). This follows from the fact that \((b-a)=-(a-b)\).

Transitive

Now, a relation is transitive if \(a \mathrel{\theta} b\) and \(b \mathrel{\theta} c\) implies that \(a \mathrel{\theta} c\) for all \(a,b,c \in S\). This means that we need to show that if \(a \equiv b \text{ mod } n\) and \(b \equiv c \text{ mod } n\), then \(a \equiv c \text{ mod } n\). Looking at this, we get that
\begin{align*}
n& | (b-a) \text{ and } \\
n&| (c-b),
\end{align*}
and we need to show that \(n| c-a\). Note that
\begin{align*}
c-a&=c+0-a \\
&=(c-b)+(b-a).
\end{align*}
Because \(n | (c-b)\) and \(n | (b-a)\) we get that \(n | c-a\) as required.

Proof of Equivalence

Let \(n \in \mathbb{Z}\) be given. Now, let \(a,b,c \in \mathbb{Z}\).

  1. Note that \(a-a=0=n*0\), so \(n | a-a\). Hence, \(a \equiv a \text{ mod } n\) for all \(a \in \mathbb{Z}\) so congruence modulo \(n\) is reflexive.
  2. Assume \(a \equiv b \text{ mod } n\). Then \(n| b-a\). Hence, \(b-a=nk\) for some \(k \in \mathbb{Z}\). We now have that
    \begin{align*}
    a-b&=-(b-a) \\
    &=-nk \\
    &=n(-k).
    \end{align*}
    Since \(-k \in \mathbb{Z}\) if \(k \in\mathbb{Z}\), we get that \(n | (a-b)\), so \(b \equiv a \text{ mod } n\). Hence congruence modulo \(n\) is symmetric.
  3. Assume that \(a \equiv b \text{ mod } n \) and \(b \equiv c \text{ mod } n\). Then \(b-a=nk_{1}\) and \(c-b=nk_{2}\) for some \(k_{1},k_{2} \in \mathbb{Z}\). Therefore,
    \begin{align*}
    c-a&=c-b+b-a \\
    &=nk_{1}+nk_{2} \\
    &=n(k_{1}+k_{2}).
    \end{align*}
    Since \(k_{1}+k_{2} \in \mathbb{Z}\) for all \(k_{1},k_{2} \in \mathbb{Z}\), we get that \(n| c-a\), so \(a \equiv c \text{ mod } n\). Therefore, congruence mod \(n\) is transitive.
  4. Because congruence modulo \(n\) is reflexive, symmetric and transitive it is an equivalence relation.

Congruence

We now have to show that congruence mod \(n\) respects addition and multiplication.

Addition

We now need to show that if \(a \equiv b \text{ mod } n\) and \(c \equiv d \text{ mod } n\), then \(a+c \equiv b+d \text{ mod } n\). That is, we can assume that \(n | b-a \) and \(n | d-c\), then we need to show that \(n| (b+d)-(a+c)\). Note this, follows since \(b+d-(a+c)=b-a+d-c\).

Proof Respects Addition

Let \(a,b,c,d \in \mathbb{Z}\) and \(a \equiv b \text{ mod } n\) and \(c \equiv d \text{ mod } n\). We then have that \(n|b-a\) and \(n|d-c\), so we may assume \(b-a=nk_{1}\) and \(d-c=nk_{2}\) for some \(k_{1},k_{2} \in \mathbb{Z}\). Hence,
\begin{align*}
(b+d)-(a+c)&=(b-a)+(d-c) \\
&=nk_{1}+nk_{2} \\
&=n(k_{1}+k_{2}).
\end{align*}
Since \(k_{1}+k_{2} \in \mathbb{Z}\), we have that \(n | (b+d)-(a+c)\). Hence, \(a+c \equiv b+d \text{ mod } n\), so congruence modulo \(n\) respects addition and is therefore a congruence relation on \(\langle \mathbb{Z}, + \rangle\).

Multiplication

In order to show that congruence modulo \(n\) respects multiplication, we need to show that, for \(a,b,c,d \in \mathbb{Z}\) with \(a \equiv b \text{ mod } n\) and \(c \equiv d \text{ mod } n\) we have that \(ac \equiv bd \text{ mod } n\). We, therefore, get to assume that \(n|b-a\) and \(n|d-c\) and we must show that \(n| (bd-ac)\). To show this, we must get a little more creative than we did last time, but we will just add a fancy zero to the equation. In this case we would note that
\begin{align*}
bd-ac&=bd-bc+bc-ac \\
&=b(d-c)+(b-a)c.
\end{align*}
While it may not be immediately clear to choose to add and subtract \(bc\), we are trying to find a way to factor out \(d-c\) and \(b-a\), so this will work quite well. We can now give a proof.

Proof Respects Multiplication

Let \(a,b,c,d \in \mathbb{Z}\) with \(a \equiv b \text{ mod }n\) and \(c \equiv d \text{ mod } n\). Then, \(n| b-a\) and \(n|d-c\), so we can let \(b-a=nk_{1}\) and \(d-c=nk_{2}\). We then have that
\begin{align*}
bd-ac&=bd-bc+bc-ac \\
&=b(d-c)+(b-a)c \\
&=bnk_{2}+nk_{1}c \\
&=n(bk_{2}+k_{1}c).
\end{align*}
Since \(bk_{2}+k_{1}c \in \mathbb{Z}\), we have that \(n| (bd-ac)\), so \(ac \equiv bd \text{ mod } n\). Therefore, congruence modulo \(n\) respects multiplication and is therefore a congruence relation on \(\langle \mathbb{Z}, \cdot \rangle\).

Kernel

Now that we know that congruence modulo \(n\) is indeed a congruence relation on \(\langle \mathbb{Z}, +\rangle\), we can find the kernel of this congruence relation. Recall that, if \(\theta\) is a congruence relation on \(S\), then \(ker(\theta)=\left\{x: x \theta e\right\}\) where \(e\) is the identity on \(S\).

In this case, we therefore want to find the set of all elements that are congruent to \(0 \text{ mod } n\). We then get that
\begin{align*}
ker=\left\{ x \in \mathbb{Z}: x \equiv 0 \text{ mod } n\right\}.
\end{align*}
As we simplify this, we note that \(x \equiv 0 \text{ mod }n\) if \(n|0-x\). That is \(n |-x\). However, \(n|-x\) if and only if \(n | x\), so the kernel will be all integers divisible by \(n\). Now, \(x\) is divisible by \(n\) if \(x=nk\) for some integer \(k\). Following this process we get
\begin{align*}
ker&=\left\{ x \in \mathbb{Z}: x \equiv 0 \text{ mod } n\right\}\\
&=\left\{x \in \mathbb{Z}: n | x \right\} \\
&=\left\{x \in \mathbb{Z}: x=nk \text{ for some } k \in \mathbb{Z}\right\} \\
&=n \mathbb{Z}.
\end{align*}

Therefore, the kernel of congruence modulo \(n\) is precisely just \(n \mathbb{Z}\).

Implications

We now know that congruence modulo \(n\) is a congruence relation on \(\mathbb{Z}\) for all \(n \in \mathbb{Z}\) for both addition and multiplication. Furthermore, the kernel of this congruence is just \(n\mathbb{Z}\).

If we note that \(\langle \mathbb{Z}, +\rangle\) is a group, we now have that the kernel of any congruence on this group must be not only a subgroup but a normal subgroup. This indeed offers us an alternative method to what we did in A Subgroup of Integers. Furthermore, since \(\langle \mathbb{Z}, +, \cdot \rangle \) is a ring, we also know that \(n\mathbb{Z}\) is an ideal of \(\mathbb{Z}\).

Conclusion

As always, I hope this helped you learn more about math and showed you how to show that a relation was a congruence relation. If you need more help, make sure to check out the other algebra posts as well as the YouTube channel!

1 thought on “Congruence Modulo n”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.