How can I show that $\begin{cases} x = 2 \pmod 6 \\ x = 5 \pmod 8 \end{cases}$ does not have a solution?

Question

I thought about using the Chinese Remainder Theorem here as $\gcd(6,8)=2$ and not $1$, but

$$\begin{cases} x = 2 \pmod 6 \\ x = 6 \pmod 8 \end{cases}$$

has indeed a solution.

But right now, I'm stuck with

$$\begin{cases} x = 2 \pmod 6 \\ x = 5 \pmod 8 \end{cases}$$

Which obviously after some calculations does not seem to have an integer solution, but how can I show it more "elegantly", like by using some theorem?

Answer 1

If you want to have a more general perspective on these examples, then you can use the following precise form of the Chinese Remainder Theorem (for the case of two equations):

Given integers $a,b$ and $m,n>0$, there is a solution to \begin{align*} x &\equiv a~(\text{mod}~m)\\ x &\equiv b~(\text{mod}~n) \end{align*} if and only if $a\equiv b~(\text{mod}~\gcd(m,n))$.

Note in the usual form of CRT one assumes $\gcd(m,n)=1$, and of course any two $a$ and $b$ are equivalent mod $1$.

However, in your case $\gcd(m,n)=\gcd(6,8)=2$. In the first set of equations you have a solution since $2$ and $6$ are equivalent mod $2$. But in the second set, $2$ and $5$ are not equivalent mod $2$, and there is no solution.

This generalizes to arbitrarily many equations. See: Chinese Remainder theorem with non-pairwise coprime moduli