0
$\begingroup$

Let n > 1 be an integer. Let $\equiv$ be the congruence relation modulo n on integer. Prove that $\equiv$ is an equivalence relation on $\mathbb{Z}$. I understand you would prove if it is reflexive, symmetric and transitive. But not sure how to approach this.

$\endgroup$
0
$\begingroup$

We have to show that congruence $\equiv$ is reflexive, symmetric, and transitive.

Reflexive: $$ x \equiv x \ ({\rm mod}\ m) $$ (Two equal numbers $x$ and $x$ give the same remainder when divided by $m$.)

Symmetric: $$ x \equiv y \ ({\rm mod}\ m) \qquad\Leftrightarrow\qquad y \equiv x \ ({\rm mod}\ m) $$ ($x$ and $y$ give the same remainder $\Leftrightarrow$ $y$ and $x$ give the same remainder when divided by $m$.)

Transitive: $$ x \equiv y \ ({\rm mod}\ m) \quad\mbox{and}\quad y \equiv z \ ({\rm mod}\ m) \qquad\Rightarrow\qquad x \equiv z \ ({\rm mod}\ m). $$ ($x$ and $y$ give the same remainder, $y$ and $z$ give the same remainder $\ \Rightarrow\ $ $x$ and $z$ give the same remainder.)

$\endgroup$
0
$\begingroup$

x≡ y (mod n) if and only if x- y is a multiple of n, x- y= kn for some integer k.

A relation, R, is "reflexive" if and only xRx for all x in the set. For any integer x, x- x= 0= 0n so this relation is reflexive.

A relation, R, is "symmetric" if and only if whenever xRy then yRx. If x≡ y then x- y= kn. In that case, y- x= -(x- y)= -kn= (-k)n so this relation is symmetric.

A relation, R, is "transitive if and only if whenever xRy and yRz then xRz. If xRy then x- y= kn. If yRz then y- z= jn. Then x- z= (x- y)- (y- z)= kn- jn= (k- j)n so this relation is transitive.

$\endgroup$
  • $\begingroup$ I dont understand how x -x = 0 ?? how'd you get that $\endgroup$ – M.Jones Apr 27 '17 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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