Equivalence Relation on Natural Numbers such that Quotient is Power of Two/Equivalence Class of Prime
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 $\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$.
Proof
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Natural Numbers such that Quotient is Power of Two.
Let $p$ be a prime number whose $\alpha$-equivalence class is $\eqclass p \alpha$.
Aiming for a contradiction, suppose $\eqclass p \alpha$ contains a prime number $q$ such that $q \ne p$.
Then:
- $p = 2^n q$
for some $n \in \Z$
If $n = 0$ then $p = q$ which contradicts $q \ne p$.
Thus $n \ne 0$.
Let $n > 0$.
Then:
- $p = r q$
for $r \in \Z$ such that $r = 2^n$.
Thus $p$ is a composite number with divisors $q$ and $r$ (and possibly more).
This contradicts the supposition that $p$ is prime.
Let $n < 0$.
Then:
- $p = \dfrac q {2^m}$
where $m = -n$ and so $m > 0$.
Thus:
- $q = r p$
for $r \in \Z$ such that $r = 2^m$.
Thus $q$ is a composite number with divisors $p$ and $r$ (and possibly more).
This contradicts the supposition that $q$ is prime.
Thus all cases of $n$ lead to a contradiction.
It follows that no $\alpha$-equivalence class can contain more than one prime number.
$\blacksquare$
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $5$