0

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

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

1 Answers1

3

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

Brian M. Scott
  • 616,228
  • 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 01: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 01:06
  • Thanks got it. I really appreciate the help. – mharris7190 Nov 20 '13 at 01:52
  • @mharris7190: You’re very welcome. – Brian M. Scott Nov 20 '13 at 01: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 02:17
  • @mharris7190: Yes. Most crucially, every prime of odd multiplicity in $a$ must have odd multiplicity in $b$ as well, and vice versa. – Brian M. Scott Nov 20 '13 at 02:20