0
$\begingroup$

Hi I am supposed to prove that R is an equivalence relation on N (natural number)

We define the relation R on N as aRb if $ab=k^2$ for some k that belongs to N.

I know that I should prove that the relation is reflexive, symmetric and transitive.

The relation is reflexive if aRa for some a that belongs to N. a^2 is a natural number and therefore a^2 = k^2 and aRa.

The relation is symmetric if aRb then bRa for all a and b that belongs to N.

The relation is symmetric because if aRb then $ab=k^2$ for some k that belongs to Z. This is equivalent to $ba= k^2$ and therefore bRa.

I'm not sure about Transitive tho. I must prove that if aRb and bRc then aRc. How can I do that?

$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

Hint. Try to prove transitivity when $a$ and $b$ are both powers of $2$. A few examples should show you how. Then think about the fundamental theorem of arithmetic.

$\endgroup$
2
  • $\begingroup$ Can you explain more? My teacher wrote a hint that if r^2 ∈ N then r ∈ Z or r does not belong to Q. How does this help me? $\endgroup$
    – Erika
    Nov 20, 2020 at 18:48
  • $\begingroup$ An integer is a square if and only if each of its prime divisors occurs to an even power. $\endgroup$
    – Ethan Bolker
    Nov 20, 2020 at 19:46
1
$\begingroup$

Since you know that aRb and bRc, you can conclude that there are natural numbers $m$ and $n$ such that $ab=m^2$ and $bc=n^2$. Your job is to prove that $ac$ is also the square of some natural number involving $m$ and $n$. (Hint: multiply those two equations together.)

$\endgroup$
5
  • $\begingroup$ If ab=m^2 and bc=n^2 then I get that ac= ((mn/b))^2. Can I say that (mn)/b is some natural number? $\endgroup$
    – Erika
    Nov 20, 2020 at 18:41
  • $\begingroup$ @Erika You know your teacher better than I do. ^_^ If this is a discrete math class, then you can probably say that. If this is a number theory class, then you should probably explain why that's true. $\endgroup$
    – user694818
    Nov 20, 2020 at 18:49
  • $\begingroup$ It is a discrete math class. But my teacher wrote as a hint on the exercise that if r^2 ∈ N then r ∈ Z or r does not belong to Q. It feels like I should do something more than what I did. $\endgroup$
    – Erika
    Nov 20, 2020 at 18:58
  • $\begingroup$ @Erika: You have $ac=\left(\frac{mn}b\right)^2$, where $ac\in\Bbb N$. Is $\frac{mn}b\in\Bbb Q$? What does this plus the hint tell you about $\frac{mn}b$? $\endgroup$
    – Brian M. Scott
    Nov 20, 2020 at 19:42
  • $\begingroup$ I think that if mn/b belongs to Q, then It is not sure that the square of mn/b will be a natural number. But if mn/b belongs to Z it must be a natural number. $\endgroup$
    – Erika
    Nov 21, 2020 at 7:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .