Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Due to my ignorance, I only superficially know the definition of congruence in number theory:

For a given positive integer $n$, two integers $a$ and $b$ are called congruent modulo $n$, written $a\equiv b\pmod{n}$ if $a−b$ is divisible by $n$ (or equivalently if $a$ and $b$ have the same remainder when divided by $n$).

Motivated by the comments and the answers to the question:

solving $x^{12}-x^{10}=2$ in the field $\mathbb {Z}_{11}$,

I'd like the post the question here:

Why is "working in $\mathbb {Z}_m$" essentially the same as "working with congruences modulo $m$"?

Edit: According to Qiaochu's comment, I added the definition of ${\mathbb Z}_n$ that I learned here.

Let $n$ be an integer greater than or equal to $2$, and consider the set ${\mathbb Z}_n=\{0,1,2,\cdots,n-1\}$. For any two integers $a$ and $b$ in ${\mathbb Z}_n$, define $a\oplus b$ to be the remainder when the usual sum, $a+b$, is divided by $n$. Then for every $a$ and $b$ in ${\mathbb Z}_n$, $a\oplus b$ is unique interger in ${\mathbb Z}_n$ that's congruent to $a+b\pmod{n}$. With this operation, $({\mathbb Z}_n,\oplus)$ is a finite Abelian group of order $n$, called the additive group of integers modulo $n$.

share|improve this question
6  
Do you understand the definition of $\mathbb{Z}_m$? –  Qiaochu Yuan Jun 16 '11 at 16:59
2  
@Jack: it's just that to me the two things you describe are the same by definition, so I'm not sure what definitions you're working with. (By the way $\mathbb{Z}_m$ is also a quotient ring, equipped with multiplication modulo $m$.) –  Qiaochu Yuan Jun 16 '11 at 17:11
1  
@Jack: more or less. So, again, not being sure what definitions you're working with I can't answer your question. –  Qiaochu Yuan Jun 16 '11 at 17:21
1  
@Jack: okay. Then all you need to know is that if $a$ is an integer, there is a unique $r \in \{ 0, 1, ... n-1 \}$ such that $a \equiv r \bmod n$, and working with $a \bmod n$ is the same as working with $r \in \mathbb{Z}_n$. –  Qiaochu Yuan Jun 16 '11 at 17:37
2  
@Jack It's difficult to give a good answer to this question knowing nothing about your level of knowledge. Are you familiar with rings and quotient sets by equivalence relations? If so, then it's not too big a leap to generalize from equivalence relations on sets to their algebraic analogs (congruences) and the notion of a quotient ring, of which $\rm\:\mathbb Z/n\:$ is a prototypical example. –  Bill Dubuque Jun 16 '11 at 18:31

4 Answers 4

up vote 10 down vote accepted

$\mathbb{Z}_m$ is defined to be the quotient $\mathbb{Z}/m\mathbb{Z}$. That is, two integers $a$, $b$ in $\mathbb{Z}_m$ are considered equal if and only if $$ a-b \in m\mathbb{Z}. $$ So this means that $a$, $b$ are equal if and only if there exists some integer $k$ such that $a-b = mk$.

Similarly, working with congruences, one has that $a\equiv b \:(\text{mod }m)$ if and only if $m | (a-b)$, which is the same as saying there exists some integer $k$ such that $a-b=mk$. In summary then, $$ a=b\text{ in }\mathbb{Z}_m \iff a-b=mk\text{ for some }k \in \mathbb{Z} \iff a \equiv b\ (\text{mod }m). $$

share|improve this answer
    
Now I see. One needs to understand the definition of ${\mathbb Z}_m$ in terms of "quotient group" for understanding the question. +1 –  Jack Jun 16 '11 at 17:14

There are many ways of thinking about $\mathbb{Z}_m$, and exactly which way you think about it may be the problem. I see from comments that you think of $\mathbb{Z}_m$ as being the set $\{0,1,2,\ldots,m-1\}$, with a special addition/multiplication defined. This is probably what is blocking your realization of the connection with congruences.

So, first, I'm going to "get to" $\mathbb{Z}_m$ from "the other end", as it were, by arriving at it by beginning from congruences, and eventually showing that you can identify it with the way you are thinking about it. Later, I will come at it from the point of view of rings, ideals, and quotients.

Starting from congruences

So let's work with the definition of congruence modulo $m$ first. I restrict to "nonnegative $m$" for convenience only; the definition does not actually require it.

Definition. Let $m$ be a nonnegative integer. We say that two integers $a$ and $b$ "are congruent modulo $m$", written $$a \equiv b\pmod{m}$$ if and only if $m|b-a$. We also say that "$a$ is congruent to $b$ modulo $m$".

Theorem. The relation "is congruent to modulo $m$" is an equivalence relation on the integers. That is:

  1. The relation is reflexive: for all integers $a$, $a\equiv a \pmod{m}$.
  2. The relation is symmetric: for all integers $a$ and $b$, if $a\equiv b\pmod{m}$, then $b\equiv a\pmod{m}$.
  3. The relation is transitive: for all integers $a$, $b$, and $c$, if $a\equiv b\pmod{m}$ and $b\equiv c\pmod{m}$, then $a\equiv c\pmod{m}$.

Proof.

  1. Since $0$ is a multiple of every integer, $m|a-a=0$ for all $a$.

  2. If $a\equiv b\pmod{m}$, then $m|b-a$. Then there exists an integer $k$ such that $mk=b-a$; therefore, $m(-k) = a-b$, so $m|a-b$, hence $b\equiv a\pmod{m}$.

  3. If $m|b-a$ and $m|c-b$, then $m$ divides the sum $(b-a)+(c-b)=c-a$, so $a\equiv c\pmod{m}$. QED

By the Fundamental Theorem of Equivalence Relations, the equivalence relation "is congruent to modulo $m$" gives a partition of $\mathbb{Z}$ into equivalence classes. Given an integer $a$, let's denote by $[a]_m$ the equivalence class modulo $m$ of $a$; that is, $$[a]_m = \{b\in\mathbb{Z}\mid a\equiv b\pmod{m}\}.$$ Note that $[a]_m=[b]_m$ if and only if $a\equiv b \pmod{m}$. If $m$ is understood from context, we will just write $[a]$.

Now we have a set that has, as its elements, the equivalence classes modulo $m$. How many elements are there?

Theorem. Let $m$ be a nonnegative integer.

  1. If $m=0$, then $[a]_m=[b]_m$ if and only if $a=b$; thus, the equivalence classes modulo $m$ are singletons, and "congruent modulo $0$" is the same as equality. The number of congruence classes modulo $0$ is $\aleph_0$, the cardinality of $\mathbb{Z}$.

  2. If $m\gt 0$, then $[a]_m=[b]_m$ if and only if the remainder of dividing $a$ by $m$ is the same as the remainder of dividing $b$ by $m$. In particular, every integer is congruent modulo $m$ to one and only one of $0$, $1$, $2,\ldots,m-1$. The number of congruence classes modulo $m$ is exactly $m$.

Proof.

  1. If $m=0$, then $a\equiv b\pmod{0}$ if and only if $0$ divides $b-a$, if and only if there exists an integer $k$ such that $0k=b-a$, if and only if $b-a=0$, if and only if $a=b$. So "congruent modulo $0$" is the same as "equal", and the rest of the clause follows.

  2. Suppose that $a\equiv b\pmod{m}$. Then $m|b-a$, so there exists an integer $k$ such that $b-a = km$. Now write $a=qm + r$, with $0\leq r\lt m$ (so that $r$ is the remainder when we divide $a$ by $m$). Then $b=km+a = km+qm+r = (k+q)m+r$. By the uniqueness of the quotient and remainder, $r$ is the remainder of dividing $b$ by $m$, so $a$ and $b$ have the same remainder.

    Conversely, suppose that $a$ and $b$ have the same remainder when divided by $m$. Then there exists $r$, $0\leq r\lt m$, and integers $q_1$ and $q_2$, such that $a=q_1m+r$ and $b=q_2m+r$. Then $b-a = (q_2m+r)-(q_1m+r) = (q_1-q_1)m$, so $m|b-a$, hence $a\equiv b\pmod{m}$.

    The possible remainders when dividing an integer by $m$ are $0$, $1$, $2,\ldots,m-1$, and each of them is their own remainder when divided by $m$. So, if $a=mq+r$, $0\leq r\lt m$, then $r$ is one and only one of $0$, $1$, $2,\ldots,m-1$, and $a$ is congruent to that. So every integer is congruent modulo $m$ to at least one of $0$, $1$, $2,\ldots,m-1$. Now suppose that $r$ and $s$ are each equal to one of $0$, $1,\ldots,m-1$, and $r\equiv s\pmod{m}$; we want to show that $r=s$. Assume without loss of generality that $s\geq r$. Then $m|s-r$; but $0\leq s-r\lt m$; the only possibility is $s-r=0$, so $s=r$.

    Thus, each of $[0]_m$, $[1]_m,\ldots,[m-1]_m$ is a distinct congruence class modulo $m$, and every congruence class modulo $m$ is one of these, so there are exactly $m$ congruence classes modulo $m$. QED

Fix $m\gt 0$. We have a set of congruence classes of integers modulo $m$. If we use the standard notation for the set of congruence classes modulo an equivalence relation, we would have to write something like: $$\mathbb{Z}/\equiv\pmod{m}\qquad\text{or}\qquad \mathbb{Z}/\equiv_m.$$ They are both somewhat clumsy, so instead we use a special symbol for this particular case: the set will be denoted $\mathbb{Z}_m$. That is: $$\mathbb{Z}_m = \Bigl\{ [a]_m \Bigm| a\in\mathbb{Z}\Bigr\}.$$

Note that every element of $\mathbb{Z}_m$ has many "names". For example, with $m=4$, we have that the element $[0]_4$ is the same as $[4]_4$, as $[8]_4$, as $[-12]_4$, and in general, $[a]_4$ is the same as $[a+4k]_4$ for any integer $k$. If we want to work with $\mathbb{Z}_m$, we have two options:

  • Keep in mind that things may have several different names; that means that if we try to define functions or properties on the elements of $\mathbb{Z}_m$, we need to make sure that they are well-defined: that they do not depend on the "name" we happen to have for the element (see below); or
  • Pick a "distinguished set of representatives." That is, pick a specific, fixed label for each of the elements of $\mathbb{Z}_m$, and stick to that label throughout. For example, one common thing to do with $\mathbb{Z}_m$ is to pick $[0]_m$, $[1]_m$, $[2]_m,\ldots,[m-1]_m$ as "distinguished labels". For $m=5$, for instance, we would stick entirely to $[0]_5$, $[1]_5$, $[2]_5$, $[3]_5$, and $[4]_5$, even though each of these classes has infinitely many other names. (sometimes it turns out to be convenient to pick as labels the labels $[a]_m$ with $|a|$ minimal; for $m=5$, for instance, one would work with $[0]_5$, $[1]_5$, $[-1]_5$, $[2]_5$, and $[-2]_5$).

(You can probably see how we're going to get to $\mathbb{Z}_m$ "being" the set $\{0,1,2,\ldots,m-1\}$...)

Now, the thing is that $\mathbb{Z}$ is not just a set; it has nice operations like $+$ and $\times$. We want to see if we can get $\mathbb{Z}_m$ to "inherit" these operations. And we can. First, let us define them using the first option above:

Definition. Let $m\gt 0$. We define "addition modulo $m$", $+_m$, to be the binary operation on $\mathbb{Z}_m$ defined by: $$[a]_m +_m [b]_m = [a+b]_m,$$ and "multiplication moudlo $m$", $\times_m$, by $$[a]_m \times_m [b]_m = [a\times b]_m,$$ where the operations on the right hand side of the definitions are the usual operations of integers.

Because every element of $\mathbb{Z}_m$ has "different names", but the definition is making use of the specific names we pick, we need to make sure that these two operations are well-defined. That is, if we replace the label $[a]_m$ by a different name for the same class, $[x]_m$, will the result of adding $[a]_m$ and $[b]_m$ be the same as the result of adding $[x]_m$ and $[b]_m$? They should, if this is going to be a function, but we don't know ahead of time because the operation is defined in terms of the label, not in terms of the object, and every object has many different labels. This is why we need to make sure the operations are well-defined. That is, we need to make sure that:

Theorem. If $[a]_m = [x]_m$ and $[b]_m = [y]_m$, then $[a+b]_m=[x+y]_m$ and $[ab]_m = [xy]_m$. That is, $+_m$ and $\times_m$ are well-defined.

Proof. Because $[r]_m = [s]_m$ if and only if $r\equiv s\pmod{m}$, the theorem is equivalent to the following two statements:

  1. If $a\equiv x\pmod{m}$ and $b\equiv y\pmod{m}$, then $a+b\equiv x+y\pmod{m}$ ("congruences modulo $m$ can be added");
  2. If $a\equiv x\pmod{m}$ and $b\equiv y\pmod{m}$, then $ab\equiv xy\pmod{m}$ ("congruences modulo $m$ can be multiplied").

Indeed, if $m|x-a$ and $m|y-b$, then $m$ divides their sum, $(x-a)+(y-b) = (x+y)-(a+b)$, hence $a+b\equiv x+y\pmod{m}$. For the multiplication clause, if $m$ divides $x-a$, then it divides $(x-a)b = xb-ab$. If $m$ divides $y-b$, then it divides $x(y-b) = xy-xb$. Since $m$ divides both $xb-ab$ and $xy-xb$, it divides their sum, so $m|(xy-xb)+(xb-ab) = xy-ab$. Therefore, $ab\equiv xy\pmod{m}$.

So $+_m$ and $\times_m$ are well-defined. QED

Now suppose you want to define addition and multiplication modulo $m$ using the second option discussed above. First, we agree on specific names for the elements of $\mathbb{Z}_m$. Let's stick to $[0]_m$, $[1]_m$, $[2]_m,\ldots,[m-1]_m$ exclusively. Then we would define: $$\begin{align*} \ [a]_m +_m [b]_m &= \left\{\begin{array}{ll} \ [a+b]_m &\text{if }0\leq a+b\lt m;\\ \ [a+b-m]_m &\text{if }m\leq a+b.\end{array}\right.\\ \ [a]_m \times_m [b]_m &= [ab-km]_m\quad\text{where }k\in\mathbb{Z}\text{ is such that }km\leq ab\lt (k+1)m. \end{align*}$$

The advantage of the second definition is that there is no doubt whatsoever that the operation is well-defined. The disadvantage is that it is hard to actually use in practice. For example, proving that $\times_m$ is associative using the first definition (once we have established it is well-defined) is very easy: it is just inherited from the fact that it is associative in $\mathbb{Z}$: $$\begin{align*} ([a]_m\times_m[b]_m)\times_m[c]_m &= [ab]_m\times_m[c]_m &\quad&\text{(by definition of )}\times_m\text{)}\\ &= [(ab)c]_m &&\text{(by definition of }\times_m\text{)}\\ &= [a(bc)]_m &&\text{(since }(ab)c=a(bc)\text{ in }\mathbb{Z}\text{)}\\ &= [a]_m\times_m[bc]_m &&\text{(by definition of }\times_m\text{)}\\ &= [a]_m\times_m([b]_m\times_m[c]_m).&&\text{(by definition of }\times_m\text{)}\end{align*}$$ Proving it using definition 2 is much more cumbersome.

But the two are completely equivalent, in the sense that you can show that they define the exact same operations on $\mathbb{Z}_m$.

Because $+_m$ and $\times_m$ are defined to be "essentially the same as" the operations $+$ and $\times$ for integers, we often drop the subindex, letting it be understood from context. So we simply write $[a]_m+[b]_m$; and if we are also dropping the $m$, to let it be understood from context, then we would simply write $[a]+[b]$.

It's not a stretch to go from there to dropping the brackets as well. So we would write $\mathbb{Z}_m = \{0,1,2,\ldots,m-1\}$ (even though we really mean the congruence classes of $0$, $1$, $2,\ldots,m-1$, not the integers themselves), and write the operations there as $+$ and $\times$ (even though we really mean the operations $+_m$ and $\times_m$ defined on congruence classes).

Quotient of a ring

In fact, the approach of having several names for each class and defining the operations on classes in terms of operations of the original set is the standard practice when constructing algebraic quotients (of groups, rings, lattices, etc).

Here, we have a ring, $\mathbb{Z}$, and an ideal $m\mathbb{Z}$ consisting of all the integers that are multiples of $m$. We use the ideal $m\mathbb{Z}$ to define an equivalence relation on $\mathbb{Z}$ by: $$a\sim b\quad\Longleftrightarrow\quad b-a\in m\mathbb{Z}.$$ Because $\mathbb{Z}$ is an ideal (in fact, it is enough that it is a subgroup for this), $\sim$ is an equivalence relation on $\mathbb{Z}$. In fact, $$a\sim b\quad\Longleftrightarrow\quad a\equiv b\pmod{m}.$$ So the quotient ring $\mathbb{Z}/m\mathbb{Z}$, consisting of the congruence classes modulo $m\mathbb{Z}$, is exactly the same as the set of congruence classes modulo $m$, $\mathbb{Z}_m$ with the operations $+_m$ and $\times_m$ that we defined above.

However, because we are defining it as a ring quotient, all the properties that are true for any ring quotient (you have a ring structure induced by the ring structure of the original ring, for example) are "automatically" true for $\mathbb{Z}_m$.

But because the two constructions yield the same underlying set with the same operations, working in the ring $\mathbb{Z}/m\mathbb{Z}$ with the induced operations is the same as working in the ring $\mathbb{Z}_m$ with the operations $+_m$ and $\times_m$, which in turn is the same as working directly with congruences modulo $m$.

Added. The fact that you have an equivalence relation that corresponds to an ideal is actually an instance of congruences (mentioned by Bill Dubuque in a comment to the original question). You can see some discussion of this in my answer to the question of why group quotients are defined only for normal subgroups. Of course, from the group point of view this doesn't matter with $\mathbb{Z}$ and $m\mathbb{Z}$, since the former is abelian so every subgroup is normal; but you can try to do the parallel development for rings and ideals and establish the same theorems. They are a special case of the more general theorems from universal algebra.

share|improve this answer
8  
Folks, I appreciate the vote of confidence, but how can someone upvote this answer less than a minute and a half after I posted it? Shouldn't one at least read through an answer before voting it up? –  Arturo Magidin Jun 16 '11 at 19:20
    
Nice post! Thank you for the elaboration! –  Jack Jun 16 '11 at 19:30
    
@Jack: One cannot tell a post is detailed unless one reads it, surely... –  Arturo Magidin Jun 16 '11 at 19:36
1  
I read through the entire post and found it most excellent. Thanks for the effort you put into it. –  ItsNotObvious Jun 16 '11 at 20:27

$\mathbb Z_n$ is usually introduced first as a finite additive group of order $n$ (which is different from the infinite group $\mathbb Z$ with addition), denoted ($\mathbb Z_n, +_n$).

To answer your question: yes, sort of. The operation on the finite group $\mathbb Z_n$ is addition modulo $n$, where $n$ is a positive integer, and the group elements can be seen as representing equivalence classes, often referred to as residue classes modulo n, where addition modulo $n$ is the equivalence relation, and such that every element of $\mathbb Z$ is congruent modulo n to exactly one of the elements of $\mathbb Z_n$. In this way, we have that all of $\mathbb Z$ can be partitioned into $n$ equivalence classes modulo $n$.

Example.
$\mathbb Z_4 = \{0, 1, 2, 3\}$ is finite cyclic group of order 4 under addition modulo $n$. $0$ is the identity element of the group, $1$ is a generator of the group (as is $3$). Every integer, when divided by $4$ or an integral multiple of $4$, has a remainder of $0$, $1$, $2$, or $3$.

Once you move beyond groups into rings and fields, you'll learn much more about $\mathbb Z_n$! Actually, you can learn much more about $\mathbb Z_n$ right here at Math.SE, simply by studying Arturo's answer to your question!

share|improve this answer

The anwer is yes because the natural map $\mathbb Z \to \mathbb Z_m$ is a ring homomorphism with kernel $m\mathbb Z$. In others words, it respects congruences modulo $m$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.