For , consider a relation on given by is a multiple of . The relation is an equivalence relation if and only if

Question

For , consider a relation  on  given by  is a multiple of . The relation  is an equivalence relation if and only if

Canvas Classes · Accepted Answer

🧠 Reflexivity Forces

The relation:  iff .

Reflexivity is the strongest constraint here. For  to be reflexive,  must hold for every :

For this to hold for all  (including  coprime to ), we need , i.e., .

So  — equivalently,  is the remainder when  is divided by .

Now verify that this same condition gives symmetry and transitivity (so the iff is justified).

Symmetric:  means . Add :  since . So , hence . ✓

Transitive:  and . Add: . Both LHS terms , so , hence . ✓

So  is necessary and s

More questions from this chapter