Equivalence Relation on Natural Numbers such that Quotient is Power of Two/One of Pair of Equivalent Elements is Divisor of the Other
Jump to navigation
Jump to search
Theorem
Let $\alpha$ denote the relation defined on the natural numbers $\N$ by:
- $\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$.
Then either:
- $c \divides d$
or:
- $d \divides c$
where $\divides$ denotes divisibility.
Proof
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.
$\blacksquare$
Sources
- 1975: T.S. Blyth: Set Theory and Abstract Algebra ... (previous) ... (next): $\S 6$. Indexed families; partitions; equivalence relations: Exercise $8$