# Define a relation $\sim$ on $\mathbb{N}$ by $a\sim b$ if and only if $ab$ is a square

(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?

• $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? – Brian M. Scott Nov 20 '13 at 0:32
• That's what I feared (written later on) but not sure how else to show it. Any ideas? – mharris7190 Nov 20 '13 at 0:33
• $aa$ is a square so $a\sim a$, so the relation is reflexive. – Michael Hardy Nov 20 '13 at 0:39
• the wikipedia page on this is really weak. Maybe I'll put in some stuff en.wikipedia.org/wiki/Square_class – 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$.

• 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. – mharris7190 Nov 20 '13 at 1:03
• @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$? – Brian M. Scott Nov 20 '13 at 1:06
• Thanks got it. I really appreciate the help. – mharris7190 Nov 20 '13 at 1:52
• @mharris7190: You’re very welcome. – Brian M. Scott Nov 20 '13 at 1:52
• 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? – 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 !!!.}}$$

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