Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
"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$.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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