Equivalence Relation on Natural Numbers such that Quotient is Power of Two/One of Pair of Equivalent Elements is Divisor of the Other
- $\forall x, y \in \N: x \mathrel \alpha y \iff \exists n \in \Z: x = 2^n y$
We have that $\alpha$ is an equivalence relation.
Let $c, d \in \N$ such that $c \mathrel \alpha d$.
- $c \divides d$
- $d \divides c$
where $\divides$ denotes divisibility.
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Natural Numbers such that Quotient is Power of Two.
We are given that $c \mathrel \alpha d$.
Without loss of generality, suppose $c < d$.
If $d < c$ then the same argument holds, mutatis mutandis.
By definition of $\alpha$, we have that:
- $c = 2^n d$
for some $n \in \Z$.
As $c < d$ it follows that $2^n > 1$.
That is, $n > 0$ and so $2^n \in \Z$.
So by definition $c$ is a divisor of $d$.
The result follows.