<s>[INST] System of two simple modular equations $$x \equiv -7 \mod 13$$
$$x \equiv 39 \mod 15$$
I need to find the smallest x for which these equations can be solved. I've been always doing this using Chinese Reminder Theorem, but it seems that it doesn't work here, I'm not sure why though. Let's see:
$N = 13*15 = 195$
$N_{1} = \frac{195}{13} = 13$
$N_{2} = \frac{195}{15} = 15$

$GCD(13, 13) = 1*13 + 0*13$
$GCD(15,15) = 1*15 + 0*15$
$$x = 1 * (-7) * 13 + 1 * 39 * 15 = 480$$

The answer however is supposed to be $x = 84$...What's wrong?
 [/INST] The way I usually go about these is to solve the two systems
$$
\mbox{$\begin{align}
x_{13}&\equiv1\pmod{13}\\
x_{13}&\equiv0\pmod{15}
\end{align}$}
\qquad\text{and}\qquad
\begin{align}
x_{15}&\equiv0\pmod{13}\\
x_{15}&\equiv1\pmod{15}
\end{align}
$$
Then combine these to get the solution to the equation given. These can both be solved at once using the Euclid-Wallis Algorithm:
$$
\begin{array}{r}
&&1&6&2\\\hline
1&0&1&-6&13\\
0&1&-1&7&-15\\
15&13&2&1&0\\
\end{array}
$$
This says that $(-6)15+(7)13=1$ which immediately gives $x_{13}\equiv(-6)15\pmod{195}$ and $x_{15}\equiv(7)13\pmod{195}$. The solution to the original question is
$$
\begin{align}
x
&\equiv-7x_{13}+39x_{15}\\
&\equiv84\pmod{195}
\end{align}
$$
Caveat: in the case of two equations as above, this only requires one application of the Euclidean algorithm. However, in the case of three or more equations, we need to apply the Euclidean algorithm once per modulus. For example, to solve
$$
\begin{align}
x&\equiv 1\pmod{3}\\
x&\equiv 2\pmod{5}\\
x&\equiv 4\pmod{7}
\end{align}
$$
we would need to solve each of
$$
\mbox{$\begin{align}
x_3&\equiv1\pmod{3}\\
x_3&\equiv0\pmod{35}
\end{align}$}
\quad\text{and}\quad
\mbox{$\begin{align}
x_5&\equiv1\pmod{5}\\
x_5&\equiv0\pmod{21}
\end{align}$}
\quad\text{and}\quad
\begin{align}
x_7&\equiv1\pmod{7}\\
x_7&\equiv0\pmod{15}
\end{align}
$$
using the Euclid-Wallis Algorithm.
</s>