Welcome guest
You're not logged in.
186 users online, thereof 0 logged in

Explanation: Explanation of Congruence Classes

What is the real meaning of the last two propositions?

In the proposition about congruence classes, we have seen that the relation $”\equiv”$ is an equivalence relation. For each integer $a\in\mathbb Z$ and each positive integer $m > 0$ there is a unique congruence class $a(m)$
$$\begin{array}{rcl}a(m)&=&\{x\in\mathbb Z\mid x\equiv a(m)\}\\
&=&\{\ldots,a-2m,a-m,a,a+m,a+2m,\ldots\}.
\end{array}$$

If another integer $a’$ can be written as $a’=a+km$ then its congruence class is
$$\begin{array}{rcl}a’(m)&=&\{\ldots,(a+km)-2m,(a+km)-m,(a+km),(a+km)+m,(a+km)+2m,\ldots\},\\
\end{array}$$
and it is easy to see that both sets are equal: $a(m)=a’(m).$ This is because both sets have infinitely many elements and those of $a’(m)$ correspond to those of $a(m)$ shifted by $k$ positions.

So, we now know what a congruence class is. But what is the quotient set $\mathbb Z_m,$ then? It is a set containing the sets like $a(m)$ as elements. The proposition about the relationship between congruences and division with quotient and remainder shows that this set is finite. If we write any given integer $a\in\mathbb Z$ in the form $$a=qm+r,\quad 0\le r < m,$$ then we will always arrive at exactly one of the values $r=0,1,2,\ldots,m-1.$ Therefore, these values can be taken as representatives of their congruence classes

$$0(m),1(m),2(m),\ldots,(m-1)(m).$$

Below, we will learn some calculation rules with congruence classes. We will see that we can add, subtract, multiply, and sometimes even divide them. And we will also see that the results of these calculations will be compatible with the same arithmetical operations done with “normal” integers, modulo the multiples of $m.$

| | | | created: 2019-04-11 22:07:08 | modified: 2019-04-11 22:07:08 | by: bookofproofs | references: [8152]


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[8152] Jones G., Jones M.: “Elementary Number Theory (Undergraduate Series)”, Springer, 1998

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.