2.3: Problem 07: Determine whether the congruences \(5x \equiv 1 \pmod{6}\),\(4x \equiv 13 \pmod{15}\) have a common solution, and find them if they exist.
Solution
For the first congruence,
$$
\begin{align*}
5x \equiv 1 \pmod{6}
\end{align*}
$$
Note that \(5\) is the inverse of \(5\) modulo \(6\). Therefore, \(x = 5\) is a solution here. For the second congruence
$$
\begin{align*}
4x \equiv 13 \pmod{15}
\end{align*}
$$
First observe that \(4\) is its own inverse module \(15\). So we can multiply both sides by \(4\) to get
$$
\begin{align*}
4 \cdot 4x &\equiv 4 \cdot 13 \pmod{15} \\
x &\equiv 52 \equiv 7 \pmod{15}
\end{align*}
$$
Therefore, \(x = 7\) is a solution. So now we have the following system of congruences
$$
\begin{align*}
x &\equiv 5 \pmod{6} \\
x &\equiv 7 \pmod{15}
\end{align*}
$$
We can’t apply CRT here since \((6,15)=3\). Therefore, we can instead use the fact that the system above has a solution if and only if
$$
\begin{align*}
5 &\equiv 7 \pmod{\gcd(6,15)} \\
5 &\equiv 7 \pmod{3}
\end{align*}
$$
But this doesn’t hold since \(5 \not\equiv 7 \pmod{3}\). Therefore, the system of congruences has no solution.