# Congruency and Congruent Classes

so studying for my midterm on Tuesday (intro to abstract algebra). The topics on the exam are Division Algorithm, Divisibility, Prime Numbers, FTA, Congruency, Congruent Classes and very brief introduction to rings.

I was reading a few theorems about Congruency and have a couple of questions.

I want to know what a "congruent class" is. My notes say "the congruence class of a modulo n" is a set:

$\left\{ \text{all } b \in \mathbb{Z} | b \equiv a \pmod{n} \right\}$ which is also saying $\left\{ \text{all } a + kn \in \mathbb{Z} | k \in \mathbb{Z} \right\}$

okay so got that. I just wrote it for some people who might need a refreshed (it is a 3rd undergrad course after all).

So in my notes our professor has a following example: $\left[ 60 \right]_{17} = \left[ 43\right]_{17}$

1) so the way I figured this out is that to check if they are equivalent, we subtract 60-43 and see if that is a multiple of n = 17. Is this how you can check if they are equal classes? If not, is there a better way to do so?

2) A certain theorem states: Let $n \in \mathbb{Z}_+; a, b \in \mathbb{Z}$ and $gcd(a,n) = d$ then $[a]x=[b]$ has exactly $d$ solutions. My question here is that is x a congruence class or a random integer? What is x and how do I solve for it?

3) Is it true that if we are in $\mathbb{Z}_{12}$ then $[7]x=[11]$ can be rewritten as $7x \equiv 11 \pmod{12}$? If so, would finding the solution be similar to solution in this question

Thankyou. I am just very confused about congurency and stuff. I understand the theorems but I am hoping someone would give me an "easy" explanation of what is going on. I still don't know the difference between circle plus and regular plus except that circle plus has to satisfy certain axioms. Am I right?

-
"I am just very confused about congurency and stuff." Don't worry, everyone is at first. Now, at least on 1) and 3) you are quite right. The method you presented in 1) is a very simple and straightforward one, and 3) can be attacked with the methods in the linked to question. For 2), I'm having some trouble with the Latex here, but it seems that $x$ is a variable, representing an integer. Actually, if you work through your 3), then you should have a concrete example of the theorem in 2) in action. –  Gunnar Þór Magnússon Nov 14 '10 at 20:30

There is a much more general definition of congruence classes, but I shall restrict to the one that is sufficient for your course. Given any integer $n$ the only possible remainders that we can get when we divide an integer $a$ by $n$ are $0,1,...,n-1$. Each set of integers which leave the same remainder on division by $n$ form what is called as a congruence class modulo $n$. All such congruence classes are mutually disjoint since a number can leave only one remainder on division by $n$. Their union is the set of all integers. Each integer in any given congruence class is said to be a representative of the class.

To check whether two integers are in the same class, we check their difference and see if it is divisible by $n$ (since the remainders of these integers cancel out when we divide by $n$). So your approach to your first question is right.

For the second question, $x$ is indeed a congruence class, since otherwise the equation does not make sense. We can define operations on the congruence classes by the correponding operations on their representatives. Its easy to check these are well defined.

-
So can you explain why [17]_8 = [1]_8? if we divide 8 by 17, the remainder is 12. if we divide 8 by 1 the remainder is 0. Yet my notes say they are the same class. –  Tyler Hilton Nov 14 '10 at 20:55
You need to take the difference of representatives and divide the difference. In this case, $17-1=16$ is divisible by $8$. Alternately, when you divide $17$ by $8$ the remainder is $1$. –  Timothy Wagner Nov 14 '10 at 21:02
@Tyler Hilton: You are interpreting it wrong. For $[17]_8$, you divide $17$ by $8$, with remainder $1$ (If you divide $8$ by $17$, then the remainder is $8$, not $12$!). Then for $[1]_8$ you divide $1$ by $8$, which gives you a remainder of $1$ as well. –  Arturo Magidin Nov 14 '10 at 22:46

Okay, let's start from the beginning. You define the congruence class of $a$ as: \begin{equation*} [a]_n = \{ b\in\mathbb{Z}\mid a\equiv a\pmod{n}\}. \end{equation*} Now, what does $a\equiv b\pmod{n}$ mean? It means that $n$ divides $a-b$, or equivalently, that $a$ and $b$ leave the same remainder when you divide them by $n$. Considering the last of the conditions, notice that:

1. Since each number leaves the same remainder as itself when divided by $n$, $a\equiv a \pmod{n}$ for all $a$.

2. If $a$ leaves the same remainder as $b$ when divided by $n$, then $b$ leaves the same remainder as $a$ when divided by $n$. So if $a\equiv b\pmod{n}$, then $b\equiv a \pmod{n}$.

3. If $a$ leaves the same remainder as $b$, and $b$ leaves the same remainder as $c$, then $a$ and $c$ leave the same remainder as well. So if $a\equiv b\pmod{n}$ and $b\equiv c\pmod{n}$, then $a\equiv c\pmod{n}$.

That means that: \begin{equation*} [a]_{n} = [b]_n\Longleftrightarrow a\equiv b\pmod{n}. \end{equation*} Why? Well, suppose the congruence classes are the same. Since $a\in[a]_n=[b]_n$, that means that $b\equiv a \pmod{n}$ (since $a\in[b]_n$), so $a\equiv b\pmod {n}$. That proves that if the classes are equal, then $a\equiv b\pmod{n}$.

Conversely, suppose that $a\equiv b\pmod{n}$. How do we prove that $[a]_{n}=[b]_{n}$? Since they are sets, the usual way is to show that each is contained in the other. If $c\in[a]_n$, then $a\equiv c\pmod{n}$ by definition; since we also have $b\equiv a\pmod{n}$ (since $a\equiv b\pmod{n}$ is our assumption), then $b\equiv c\pmod{n}$, so $c\in[b]_n$. Therefore, every that is in $[a]_{n}$ is also in $[b]_n$, so $[a]_n\subseteq [b]_n$. For the converse inclusion, if $c\in[b]_n$, then $b\equiv c\pmod{n}$, and since we also have $a\equiv b\pmod{n}$, then $a\equiv c \pmod{n}$ so $c\in[a]_n$. Therefore, $[b]_n\subseteq [a]_n$. Since we have the two inclusions, we conclude that $[a]_n=[b]_n$.

We also have the following, which is perhaps more surprising: \begin{equation*} [a]_n\cap[b]_n\neq\emptyset\Longleftrightarrow [a]_n=[b]_n. \end{equation*} That is: the only way the class of $a$ and the class of $b$ have anything in common is if they are identical. Why? Well, if they are identical they certainly have nonempty intersection, since the class of $a$ always includes at least $a$. And conversely, if $c\in[a]_n\cap[b]_n$, then $a\equiv c\pmod{n}$ and $b\equiv c\pmod{n}$, from which we conclude that $a\equiv b\pmod{n}$, so $[a]_n=[b]_n$ by what we just finished proving.

(1) How do we check if $[a]_{17} = [b]_{17}$? Precisely the way you did it: the classes are equal if and only if $a\equiv b \pmod{17}$. How do you check if $a\equiv b\pmod{17}$? By checking to see if $17$ divides $a-b$. So how do you check in general whether $[a]_n=[b]_n$? You check to see if $a-b$ is a multiple of $n$. If it is, then the classes are equal. If $a-b$ is not a multiple of $n$, then they are not equal, and in fact they are disjoint.

There are other ways: for example, if you could show that $[60]_{17}$ and $[43]_{17}$ have any element in common, then you would be able to conclude that they are equal. Sometimes it may be simpler to see that $[a]_n$ and $[b]_n$ have some element in common than to check if $n$ divides $a-b$; but the standard way of checking is to see whether $n$ divides $a-b$, just as you did.

(2) What you have is an equation in which $x$ is an unknown. You are really looking for all solutions to the congruence \begin{equation*} ax \equiv b \pmod {n} \end{equation*} That is, all integers $x$ that make the congruence true. For example, $x=3$ is a solution to \begin{equation*} 2x \equiv 1 \pmod{5} \end{equation*} because $(2)(3)= 6\equiv 1 \pmod{5}$. In fact, because $3$ is a solution, so is $3+5k$ for any integer $k$; that is, any element in $[3]_5$ is a solution, since $3$ is a solution. So the solutions will actually be a collection of congruence classes.

Moreover, if we replace $2$ in the equation with $7$, so that we are trying to solve $7x\equiv 1 \pmod{5}$, then anything which was a solution to $2x\equiv 1\pmod{5}$ is still a solution, and any solution to the first one is still a solution to the new congruence; why? because $2x\equiv 7x\pmod{5}$ for all $x$, as $2x-7x = -5(x)$ is always a multiple of $5$. So we can replace $2$ with any element of $[2]_5$ and not change the solutions. Likewise, we can replace $1$ with any element of $[1]_5$ and not change the solutions. So it's almost as if instead of trying to solve the single congruence \begin{equation*} 2x \equiv 1 \pmod{5} \end{equation*} we are trying to solve the equation \begin{equation*} [2]_5 x = [1]_5 \end{equation*} So that's why you have written $[a]x=[b]$. That really means the congruence $ax\equiv b \pmod{n}$.

What you wrote, however, is incorrect. You are missing a clause: the congruence will have $d$ solutions if $d$ divides $b$. Otherwise, it's not going to have any. For an easy example, consider the congruence $2x\equiv 1 \pmod{4}$. Then $\gcd(2,4)=2$, but there are no solutions to the congruence, because $2x$ is always even, so $2x-1$ is always odd, so $4$ never divides $2x-1$.

Now, how do you solve a congruence $ax\equiv b\pmod{n}$ when $\gcd(a,n)$ divides $b$? let $d=\gcd(a,n)$. Then we can write $a=da'$, $b=db'$, and $n=dn'$. Then $ax\equiv b\pmod{n}$ if and only if $n$ divides $ax-b$. But $ax-b = d(a'x - b')$, and $dn'$ divides $d(a'x-b')$ if and only if $n'$ divides $a'x-b'$, if and only if $a'x\equiv b'\pmod{n'}$. So if we can solve a congruence when $\gcd(a,n)=1$, then we can solve any congruence where $\gcd(a,n)$ divides $b$

So, how do you solve a system $ax \equiv b\pmod{n}$ when $\gcd(a,n)=1$ (which will of course divide $n$)? Since $\gcd(a,n)=1$, then we can write $n$ as a linear combination of $a$ and $n$, $1=ar+ns$ for some integers $r$ and $s$ (for example, using the Euclidean algorithm). Multiplying through by $b$ you get $b=a(rb)+ n(sb)$. That means that $n(sb) = a(rb)-b$, so $a(rb)\equiv b \pmod{n}$, which means that $x=rb$ is a solution. If $y$ is any other solution, then $ay\equiv b\pmod{n}$, and $ax\equiv b\pmod{n}$, so $ax\equiv ay\pmod{n}$, hence $n$ divides $ax-ay=a(x-y)$, and since $\gcd(a,n)=1$, then $n$ divides $x-y$; so if $y$ is any other solution, then $x\equiv y\pmod{n}$. So the only congruence class that is a solution is $[x]_n$.

Now, what about general congruences? Suppose you have $[a]_nx=[b]_n$ and $\gcd(a,n)=d$ divides $b$. Write $a=da'$, $b=db'$, and $n=dn'$. Notice that $\gcd(a',n')=1$. Find a solution $x_0$ to $[a']_{n'}x=[b']_{n'}$. Then $n'$ divides $a'x_0 -b'$, so $dn'=n$ divides $d(a'x_0-b') = da'x_0-db' = ax_0-b$. So $x_0$ is also a solution to the original problem. If $y$ is any other solution, then as before we get that $n$ divides $a(x_0-y)$; so $dn'$ divides $da'(x_0-y)$, hence $n'$ divides $a'(x_0-y)$, and since $\gcd(a',n')=1$, then $n'$ divides $x_0 - y$; that is, $y\equiv x_0\pmod{n'}$, so $y=x_0+kn'$ for some $k$. Conversely, if $y = x_0+\ell n'$ for some $\ell$, then \begin{equation*} ay = a(x_0+\ell n') = ax_0 + \ell an' = ax_0 + \ell (da')n' = ax_0 + \ell a'(dn') = ax_0 + (\ell a')n, \end{equation*} which says that $ay \equiv ax_0 \pmod{n}$, so $y$ is also a solution. So what are the different solutions? Well, we have $x_0$, $x_0+n'$, $x_0+2n'$, $x_0+3n',\ldots, x_0+(d-1)n'$. All of these are not congruent to one another modulo $n$; the "next" one, however, will be $x_0+dn' = x_0+n$, which is congruent to $x_0$ modulo $n$. So the only distinct congruence classes that are solutions are $[x_0]_n$, $[x_0+n']_n,\ldots,[x_0+(d-1)n']_n$, giving you exactly $d$ distinct classes that are solutions to $[a]_nx=[b]_n$.

To see this in practice, take $n= 77$, $a=21$, and $b=14$. We want to solve the system $[21]_{77} x = [9]_{77}$ Since $\gcd(77,21)=7$ divides $b$, the system has solutions; in fact, it has $7$ different congruence classes modulo $77$ as solutions.

So, we write $21 = 7\cdot 7$, $14 = 7\cdot 2$, $77 = 7\cdot 11$. And we first solve the system $[3]_{11}x=[2]_{11}$. To do this, we write $1$ as a linear combination of $3$ and $11$, like so: $1 = 3(4) - 11(1)$. Then multiply by $2$ to get $2 = 3(8)-11(2)$. So $x_0=8$ is a solution (indeed, $3(8)=24\equiv 2\pmod{11}$). Now going back to the original congruence, we take $x_0$ and we add multiples of $11$ (why $11$? Because $n=77$ is $7\cdot 11$, and $7$ is the $d$ from before) until we have our $7$ different solutions. So the solutions are: $[8]_{77}$, $[19]_{77}$, $[30]_{77}$, $[41]_{77}$, $[52]_{77}$, $[63]_{77}$, and $[74]_{77}$. You can verify that they all are solutions to $[21]_{77}x = [14]_{77}$. For example, $21\cdot 41 = 861$, and $[861]_{77}=[14]_{77}$ because $861-14 = 847 = 77\cdot 11$.

(3) Yes: that is exactly the meaning of $[a]_nx=[b]_n$; it means $ax\equiv b\pmod{n}$.

Hope this helps, despite the length.

-