# Equivalence Relation on Natural Numbers such that Quotient is Power of Two

## 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$

Then $\alpha$ is an equivalence relation.

### Equivalence Class Contains 1 Odd Number

Let $\eqclass n \alpha$ be the $\alpha$-equivalence class of a natural number $n$.

Then $\eqclass n \alpha$ contains exactly $1$ odd number.

### Equivalence Class of Prime

Let $\eqclass p \alpha$ be the $\alpha$-equivalence class of a prime number $p$.

Then $\eqclass p \alpha$ contains no other prime number other than $p$.

### Smallest Equivalence Class with no Prime

Let $\eqclass x \alpha$ denote the $\alpha$-equivalence class of a natural number $x$.

Let $r$ be the smallest natural number such that $\eqclass r \alpha$ contains no prime number.

Then $r = 9$.

### One of Pair of Equivalent Elements is Divisor of the Other

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

Checking in turn each of the criteria for equivalence:

### Reflexivity

We have that for all $x \in \N$:

$x = 2^0 x$

and as $0 \in \Z$ it follows that:

$x \mathrel \alpha x$

Thus $\alpha$ is seen to be reflexive.

$\Box$

### Symmetry

 $\displaystyle x$ $\alpha$ $\displaystyle y$ $\displaystyle \leadsto \ \$ $\displaystyle x$ $=$ $\displaystyle 2^n y$ for some $n \in \Z$ $\displaystyle \leadsto \ \$ $\displaystyle y$ $=$ $\displaystyle 2^{-n} x$ dividing both sides by $2^{-n}$ $\displaystyle \leadsto \ \$ $\displaystyle y$ $\alpha$ $\displaystyle x$ as $-n \in \Z$

Thus $\alpha$ is seen to be symmetric.

$\Box$

### Transitivity

Let $x \mathrel \alpha y$ and $y \mathrel \alpha z$.

Then by defintion:

 $\displaystyle y$ $=$ $\displaystyle 2^m z$ for some $m \in \Z$ $\displaystyle x$ $=$ $\displaystyle 2^n y$ for some $n \in \Z$ $\displaystyle$ $=$ $\displaystyle 2^n \paren {2^m z}$ $\displaystyle$ $=$ $\displaystyle 2^{n + m} z$ $\displaystyle \leadsto \ \$ $\displaystyle x$ $\alpha$ $\displaystyle z$ as $n + m \in \Z$

Thus $\alpha$ is seen to be transitive.

$\Box$

$\alpha$ has been shown to be reflexive, symmetric and transitive.

Hence by definition it is an equivalence relation.

$\blacksquare$