2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Nov 17, 2020 at 2:18
  • $\begingroup$ @JMoravitz Is it necessary to cite FTOA to show reflexivity/symmetry here? $\endgroup$
    – mathstudent288
    Nov 17, 2020 at 2:22
  • 4
    $\begingroup$ 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 $\endgroup$
    – JMoravitz
    Nov 17, 2020 at 2:29

1 Answer 1

Reset to default
0
$\begingroup$

$ \newcommand{\p}[1]{\prod_i p_i^{#1_i}} \newcommand{\s}[1]{\sum_i #1_i} $ This is more or less correct; the main remaining issue, as noted in the comments, is to use that the fundamental theorem of arithmetic ensures the uniqueness of the prime factorization. (Your relation is not only relative to the sums of the exponents, but a priori also relative to the primes $p_i$ you use.) Then each property follows easily:

  • 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$.

Mostly just posting this to get this out of the unanswered queue. Posting as Community Wiki in particular since I have nothing further to add.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.