# Equivalence relation: $(n,m) \in S \textrm{ if$m^2$is divisible by } n$

How can I show that $S$ is an equivalence relation:

Given a relation $S$ on $\mathbb N$ such that:

$$(n,m) \in S \text{ if } m^2 \text{ is divisible by } n$$

I know equivalence relations are symmetric, reflexive and transitive. I'm just not sure how to use this knowledge to prove it.

Reflexive:
I believe I need to show that for any $x \in \mathbb N$, $(x\,,\,x) \in S$.

I'm unsure how I prove this for reflexive, symmetric, and transitive.

• Use $\in$ for $\in$. – Shaun Jun 3 '18 at 11:43

Reflexivity: $(n,n) \in S$ for each $n$. Ask yourself: is it true that $n^2$ is a multiple of $n$? If yes, you have reflexivity.
Symmetry: if $(n,m) \in S$ then $(m,n) \in S$. Ask yourself: assume that $m^2$ is a multiple of $n$. Is it true that $n^2$ is a multiple of $m$? If yes, you have symmetry.
Transitivity: if $(n,m) \in S$ and $(m,l) \in S$, then $(n,l) \in S$. Ask yourself: if $m^2$ is a multiple of $n$ and $l^2$ is a multiple of $m$, is it true that $l^2$ is a multiple of $n$? If yes, you have transitivity.