(a) Show that $\sim$ is an equivalence relation on $\mathbb{N}$.

(b) Describe the equivalence classes [3], [9], and [99].

(c) If $a\sim b$, which attributes of $a \text{ and } b$ are equal?

For (a) I have to show that $\sim$ is reflexive, transitive, and symmetric in order for it to be an equivalence relation.

So if $ab$ is square, $a = b$ so the relation is reflexive. Next, take $a\sim b$ and $b \sim c$, because $ab$ is square and $bc$ is square, $a = b = c$, so $a = c$. Thus $\sim$ is transitive. For symmetric, I'm not sure. But before I continue, can I even say that if $ab$ is square, $a = b$. I was thinking of $16 = 2 \cdot 8$ which seems like $a$ and $b$ are not equal but is that just a square number or a square? Is there a difference?

If I can't do that, how am I supposed to go about it?

  • $\begingroup$ $4\cdot9=36$ is a square, but $4\ne 9$, so your argument for reflexivity doesn’t work. In fact as you noticed, $2\sim 8$, even though $2\ne 8$. Do you want to go back and rethink this a bit, or do you want me to write an answer pointing you in the right direction? $\endgroup$ – Brian M. Scott Nov 20 '13 at 0:32
  • $\begingroup$ That's what I feared (written later on) but not sure how else to show it. Any ideas? $\endgroup$ – mharris7190 Nov 20 '13 at 0:33
  • 1
    $\begingroup$ $aa$ is a square so $a\sim a$, so the relation is reflexive. $\endgroup$ – Michael Hardy Nov 20 '13 at 0:39
  • $\begingroup$ the wikipedia page on this is really weak. Maybe I'll put in some stuff en.wikipedia.org/wiki/Square_class $\endgroup$ – Will Jagy Nov 20 '13 at 0:46

I’ll get you started. To show that $\sim$ is reflexive, you must show that if $n\in\Bbb N$, then $n\sim n$. Check the definition of $\sim$: this means that $n\cdot n$ is a square. Of course $n\cdot n=n^2$ is a square, so $n\sim n$, and $\sim$ is reflexive. You should have no trouble showing that $\sim$ is symmetric. For transitivity, suppose that $k\sim m$ and $m\sim n$. Then $km$ and $mn$ are squares, say $km=a^2$ and $mn=b^2$; you must show that $k\sim n$, i.e., that $kn$ is a square. Try to write $kn$ in terms of the pieces that you already have, doing it in a way that demonstrates that $kn$ is a square.

$[3]$ is by definition the set of all $n\in\Bbb N$ such that $3\sim n$, i.e., such that $3n$ is a square. What does this tell you about $n$? HINT: What can you say about the number of factors of $3$ in the prime factorization of $n$? Thinking in similar terms will get you through the rest of (b) as well.

For (c) you should be thinking about the prime factorizations of $a$ and $b$.

  • $\begingroup$ If $km$ and $mn$ are square, they have an even multiplicity of prime factors. So I want to show that $kn$ has an even multiplicity of prime factors. I'm stuck at that point. Any help. $\endgroup$ – mharris7190 Nov 20 '13 at 1:03
  • $\begingroup$ @mharris7190: Suppose that $p$ is a prime that appears an odd number of times in $m$; then it must appear an odd number of times in both $k$ and $n$. (Why?) And if $p$ appears an even number of times in $m$, then it appears how in $k$ and $n$? $\endgroup$ – Brian M. Scott Nov 20 '13 at 1:06
  • $\begingroup$ Thanks got it. I really appreciate the help. $\endgroup$ – mharris7190 Nov 20 '13 at 1:52
  • $\begingroup$ @mharris7190: You’re very welcome. $\endgroup$ – Brian M. Scott Nov 20 '13 at 1:52
  • $\begingroup$ I'm not sure how to answer 3. I want to say that the multiplicity of the prime factors of a and b have the same parity. Is this what the question is looking for? $\endgroup$ – mharris7190 Nov 20 '13 at 2:17

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$ Given $a, b \in {\mathbb N}$: $$ \left. \begin{array}{rclcc} a \sim b & \imp & \exists\ m \in {\mathbb N} & \ni & ab = m^{2} \\ b \sim c & \imp & \exists\ n \in {\mathbb N} & \ni & bc = n^{2} \end{array}\right\rbrace \quad\imp\quad ac = {m^{2} \over b}\, {n^{2} \over b} = \left(mn \over b\right)^{2}\tag{1} $$ $$ \pars{1}\quad\not\!\Longrightarrow\quad a \sim c\quad \mbox{unless}\quad \left.b\,\right\vert \left(mn\right)\quad {\large\tt\mbox{which is not always true !!!.}} $$

  • $\begingroup$ Is this true? Thanks! $\endgroup$ – mharris7190 Nov 20 '13 at 1:09
  • $\begingroup$ Funny characters and exclamations notwithstanding, it is "always true" that $b$ divides $mn$ (hence $a\sim c$). $\endgroup$ – Did Nov 23 '13 at 10:19

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.