# Showing that a relation tied to prime factorization is an equivalence relation

Consider the relation $$≈$$ on $$ℕ$$:

If $$x = {p_1}^{x_1} \times {p_2}^{x_2} ... \times {p_k}^{x_k}$$ and $$y = {p_1}^{y_1} {p_2}^{y_2} ... {p_k}^ {y_k}$$ , where $$p_i$$ are distinct primes and $$x_i$$ and $$y_i$$ are nonnegative integers, then $$x ≈ y$$ iff $$x_1 + x_2 + \ldots + x_k = y_1 + y_2 +\ldots + y_k$$.

Show $$≈$$ is an equivalence relation

I know I need to show reflexivity, symmetry, and transitivity.

For reflexivity I have $$x ≈ x \iff x_1 + x_2 + \ldots + x_k = x_1 + x_2 + \ldots + x_k$$, which is clearly true.

And for symmetry I have $$x ≈ y \implies y ≈ x$$,

so

\begin{align*} &x_1 + x_2 + \ldots + x_k = y_1 + y_2 +\ldots + y_k \\ \implies &y_1 + y_2 +\ldots + y_k = x_1 + x_2 + \ldots + x_k \end{align*}

which is also clearly true.

This seems too easy and I feel like I'm doing this wrong.

• There is also a major inbetween step which you have skipped and that is citing the fundamental theorem of arithmetic that such a representation of $x$ as $p_1^{x_1}\times \dots \times p_k^{x_k}$ is effectively unique. Nov 17, 2020 at 2:18
• @JMoravitz Is it necessary to cite FTOA to show reflexivity/symmetry here? Nov 17, 2020 at 2:22
• Write the proof with your audience in mind. To some readers, perhaps not. I would though, personally. Especially for transitivity because $x\approx y$ might mean that $x=p_1^{x_1}\times\dots p_k^{x_k}$ and $y=p_1^{y_1}\times\dots p_k^{y_k}$ with $x_1+\dots+x_k=y_1+\dots+y_k$ but $y\approx z$ might instead mean that $y=q_1^{y'_1}\times \dots \times q_{\ell}^{y'_{\ell}}$ and $z=q_1^{z_1}\times\dots q_{\ell}^{z_\ell}$. Without FTOA how would you know that the representations $p_1^{y_1}\times\dots \times p_k^{y_k}$ and $q_1^{y'_1}\times \dots \times q_{\ell}^{y'_\ell}$ are effectively the same Nov 17, 2020 at 2:29

• Reflexivity: Since $$x = \prod_i p_i^{x_i}$$ (and this is the only representation of $$x$$ for the primes $$p_i$$, up to having $$x_i = 0$$ for some $$i$$'s) and $$\sum_i x_i = \sum_i x_i$$ trivially, $$x \approx x$$.
• Symmetry: Assume $$x \approx y$$. Since $$x = \prod_i p_i^{x_i}$$ and $$y = \p y$$, then $$\s x = \s y$$. Equality is a symmetric relation, so $$\s y = \s x$$, and the prime decomposition is the only one, so $$y \approx x$$.
• Transitivity: Assume $$x \approx y$$ and $$y \approx z$$. Then we may write $$x,y,z$$ uniquely by $$x = \p x$$, $$y = \p y$$, and $$z = \p z$$. By assumption, $$\s x = \s y$$ and $$\s y = \s z$$. By the transitivity of equality, $$\s x = \s z$$, and, alongside the uniqueness of the prime decomposition, this ensures $$x \approx z$$.