Question 1195956: Let n be a fixed positive integer in Z. Define the relation ≡n on Z by
x ≡n y if and only if n|(x − y) for any x, y ∈ Z. Show that ≡n is an equivalence
relation
Answer by math_tutor2020(3817)   (Show Source):
You can put this solution on YOUR website!
I'll use the tilde mark ~ in place of the symbol ≡n
So x ~ y means n | (x-y) and that is saying "n divides (x-y)"
i.e. "n is a factor of (x-y)"
Furthermore n|(x − y) is the same as nk = x-y for some integer k
Here's an article talking about Equivalence Relations
https://www.cuemath.com/algebra/equivalence-relations/
We need to prove three things:
Reflexive
Symmetric
Transitive
----------------------------------------------------------
Reflexive:
Let 'a' be an integer
The claim is to show that a ~ a is true
Well,
x ~ y
nk = x-y
nk = a-a
nk = 0
Since n is positive, this means k = 0 must be the case.
Therefore, a ~ a is true and the relation has been proven to be reflexive.
-------------------
Symmetric:
Define two integers. Call them a and b.
We need to show that if a ~ b, then b ~ a
Start with a ~ b and follow these steps
a ~ b
n | (a-b)
nk = a-b
-1*nk = -1(a-b)
n(-k) = -1(a-b)
n(-k) = -a+b
n(-k) = b-a
n | (b-a)
b ~ a
I multiplied both sides by -1 and did a bit of rearranging to get -nk into n(-k)
The k isn't that special since the nk is really n*(some integer)
k is an integer, and so is -k.
We have shown that a ~ b leads to b ~ a; hence proving the symmetric argument.
-------------------
Transitive:
We'll need three integers this time. Call them a,b,c
If a ~ b and b ~ c, then it should lead to a ~ c
a ~ b leads to nk = a-b for some integer k
while b ~ c leads to nm = b-c for some integer m
Add the equations and do a bit of algebra
(nk) + (nm) = (a-b) + (b-c)
n(k+m) = a-c
n*(some integer) = a - c
n | (a-c)
a ~ c
Therefore, a ~ b and b ~ c does indeed point to a ~ c
The transitive aspect has been proven.
----------------------------------------------------------
We have proven the three properties of reflexive, symmetric, and transitive.
Therefore, the relation has been proven to be an equivalence relation.
Side note: For more information, check out the concept about congruence mod n.
|
|
|
