0

Let $n,m \in \mathbb N$. Let further $k \in \mathbb N_0$ be such that $km \leq n <(k+ 1)m$.
We define the modulo operation $n \pmod{m}$ to be $n \pmod{m}:=n−km$.
Now define for a fixed $m \in \mathbb N$ define $l \sim j$ if $l \pmod{m}=j \pmod{m}$.
Show that this defines an equivalence relation on $\mathbb N$.

I'm trying to solve this task ,but I'm not sure if this is all what I need to show

my answer :

to show that there is an Equivalence relation we should show three things:

(1) a ~ a (reflexive property).
a= l mode m. => l mod m = l mod m.(reflexive )

(2) if a ~ b then b ~ a (symmetric property).
a= l mode m "and" b = j mode m => l mod m = j mode m "and" j mode m= l mod m .(Symmetry)

(3) if a ~ b and b ~ c then a ~ c (transitive property).
a= l mode m "and" b = j mode m "and" c = d mod m where d ∈ N
suppose l mod m = j mode m "and" j mode m = d mod m ==> l mod m = d mod m.(transitive)

amrsa
  • 12,917
Alaa Alsayed
  • 5
  • 5

1 Answers1

0

It all follows simply from the fact that equality is an equivalence relation.

Then, for reflexivity, $a \sim a$ because $a \pmod{m} = a \pmod{m}$.
For symmetry, \begin{align} a \sim b &\Longrightarrow\; a \pmod{m} = b \pmod{m} \\ &\Longrightarrow\; b \pmod{m} = a \pmod{m} \\ &\Longrightarrow\; b \sim a. \end{align} For transitivity, if $a \sim b$ and $b \sim c$, then $$a \pmod{m} = b\pmod{m} \qquad\text{ and }\qquad b\pmod{m} = c\pmod{m},$$ whence $a\pmod{m} = c\pmod{m}$ and $a \sim c$.

As you can see, the result is rather trivial, provided you have already proved, or you are given that $n \mapsto n\pmod{m}$ is indeed an operation.

amrsa
  • 12,917