How to prove $ (3\Bbb N + 1) \cap (5\Bbb N + 3) = 15\Bbb N + 13$ I'm trying to prove that: $$ (3\Bbb N + 1) \cap (5\Bbb N + 3) = 15\Bbb N + 13$$ What have I done so far is, I'm getting an x from left hand side of equation:
$$
x \in (3\Bbb N + 1) \cap (5\Bbb N + 3)
$$
Then I'm simplifying it, like this:
$$
x \in (3\Bbb N + 1) \land x \in (5\Bbb N + 3)
$$
$3\Bbb N + 1$ is basicly $1 \pmod{3}$, and $(5\Bbb N + 3)$ is basicly $3 \pmod{5}$, thus:
$$
x \equiv 1 \pmod{3} \; and \; x\equiv 3 \pmod{5}
$$
Use CRT (i.e. https://en.wikipedia.org/wiki/Chinese_remainder_theorem) to conclude result for left hand side:
$$
a_1 = 1, \; m_1 = 5, \; y_1 \equiv 2 \pmod{3}
$$
After that,  Use CRT to conclude result for right hand side:
$$
a_2 = 3, \; m_2 = 3, \; y_2 = 2 \pmod{5}
$$
Then plug in:
$$
\begin{split}
x &\equiv a_1m_1y_1 + a_2m_2y_2 \pmod{M} \\
  & \equiv 1\cdot 5\cdot 2 + 3\cdot 3 \cdot 2 \pmod{3\cdot 5} \\
  & \equiv 28 \pmod{15}
    \equiv 13 \pmod{15} 
\end{split}
$$
then find for the right side;
$$
x \in (15\Bbb N + 13) \implies x = 13 \pmod{15}
$$
Did I prove it right? Is there an easier way to do this?

Let $n=3x+1$ and assume $x=5y+z$, then $n=15y+3z+1$. If $n\equiv 3 \pmod{5}$, then $z\equiv -1 \pmod5$. Thus we can take $z=-1$ and obtain the result you want.
