1

I have the following exercise: In set $X$, let $\mathrel{R_1}$ be the congruence relation modulo 2, and let $\mathrel{R_2}$ be the relation of congruence modulo 3. Determine $\mathrel{R_1}\circ\mathrel{R_2}$.

And i think that in my solution I did not reach the simplest possible form.

Here's my solution:

$x \mathrel{R_1} y \Leftrightarrow x \equiv y \pmod{2}$

$x \mathrel{R_2} y \Leftrightarrow x \equiv y \pmod{3}$

then:

$x \ (\mathrel{R_1}\circ\mathrel{R_2}) \ y \Leftrightarrow \exists_{a \in X}(x \mathrel{R_1} a \wedge a \mathrel{R_2} y) \Leftrightarrow \exists_{a \in X}([x \equiv a \pmod{2}] \wedge [a \equiv y \pmod{3}])$

Is $\exists_{a \in X}([x \equiv a \pmod{2}] \wedge [a \equiv y \pmod{3}])$ the farthest we can go?

Asaf Karagila
  • 393,674
schmidt1995
  • 11
  • If $X=\Bbb Z$ or $\Bbb N$ you can go much farther using the Chinese remainder theorem. Else, it depends on $X.$ – Anne Bauval Jan 05 '23 at 12:29
  • So after applying this theroem we get that this relation can be written like this: $\exists_{z\in X}(z = (3x+4y)\pmod{6})$. Am i right? – schmidt1995 Jan 05 '23 at 13:32
  • Yes, so if $X$ contains at least one element of each class mod 6 then this relation is simply: $x$ and $y$ are always related. Don't you have any information on $X$ in your exercise? – Anne Bauval Jan 05 '23 at 13:40
  • Unfortunately no, it just says: In set $X$ ..., but I'm still a bit anxious about that $z = (3x + 4y) \pmod{6}$, did I solve it correctly? – schmidt1995 Jan 05 '23 at 13:47
  • Yes you did: by the CRT, for any integers x,y, there is a unique integer z mod 6 s.t. z=x mod 2 and z=y mod 3, and you found one. – Anne Bauval Jan 05 '23 at 13:52
  • 1
    Big thanks for help, really appreciate it. – schmidt1995 Jan 05 '23 at 13:54

0 Answers0