# Is “$x\sim y$ iff $x$ and $y$ have the same powers of $p$ dividing them” an equivalence relation?

Let $p\in\mathbb N$ be a prime number and define for $x,y\in\mathbb N$, $$x\sim y\iff (p^n|x \iff p^n|y \text{ for all }n\in\mathbb N).$$ The vertical bar $|$ denotes the divisor-operation. Is $\sim$ an equivalent relation on $\mathbb N$? I've already shown reflexivity and symmetry, but I'm stuck on the transitive property.

-
"For all $n \in \mathbb N$?" The only integers $x$ and $y$ satisfying this for all $n$ is the number zero. What do you want exactly? – Patrick Da Silva Jun 2 '12 at 16:44
I imagine what gary means is to have "if and only if" in place of "and". – MJD Jun 2 '12 at 16:47
I still don't get it? – M.B. Jun 2 '12 at 16:54
@M.B. The condition is just saying that (for the fixed prime $p$) the highest power of $p$ going into $x$ and $y$ is the same. – Zev Chonoles Jun 2 '12 at 16:56
Ah, $p$ is fixed. I missed that. – M.B. Jun 2 '12 at 16:57

This is a special case of the equivalence relation induced by a function $f:X\to Y$, defined by saying that $a\sim b$ if and only if $f(a)=f(b)$. In your case, the function would send $x\in\mathbb{N}$ to the largest $n$ such that $p^n|x$, or the valuation of $x$ at $p$. Two numbers $x$ and $y$ satisfy the property $$\forall(n\in\mathbb{N}),\ p^n|x\leftrightarrow p^n|y$$ if and only if they have the same valuation at $p$.
Said another way, "$x\sim y$ iff $x$ and $y$ have the same whatever" is an equivalence relation pretty much no matter what you put in for "whatever". – Gerry Myerson Jun 3 '12 at 0:01
If $x\sim y$ and $y\sim z$, then for any $n\in\mathbb{N}$, $$p^n\mid x\iff p^n\mid y\qquad\text{and}\qquad p^n\mid y\iff p^n\mid z.$$ Therefore $p^n\mid x\iff p^n\mid z$, so that $x\sim z$.