# Congruence system doesn't hold, though it should?

Determine all the $a \in \mathbb Z$ such the equation system is compatible in $\mathbb Z$

$$\begin{cases} 6x \equiv a^{121} \pmod {20} \\ 14x \equiv 3 \pmod {15} \end{cases}$$

So, piece of cake, I just use the Chinese remainder theorem:

$$\begin{cases} 6x \equiv a^{121} \pmod 4 \\ 6x \equiv a^{121} \pmod 5 \end{cases}$$

$$\begin{cases} 14x \equiv 3 \pmod 5 \\ 14x \equiv 3 \pmod 3 \end{cases}$$

By the CRT, the system will have an assured solution if

$$\begin{cases} 14x \equiv 3 \pmod 5 \\ 6x \equiv a^{121} \pmod 5 \end{cases}$$

is consistent. Using some basic properties and the fermat theorem, I finally get:

$$a \equiv 2 \pmod 5$$

So for any given $a$ the the system should work, shouldn’t it?

BUT if I take $a = 7$, it assures the condition, but $6x \equiv a^{121}\equiv3 \pmod 4$ will be impossible to solve.

What am I doing wrong?

• One needs to pay attention to the mod $4$ part. – André Nicolas Dec 18 '13 at 16:50
• But $7^{121} \equiv 7 \pmod{20}$, not $3$. – Daniel Fischer Dec 18 '13 at 16:52
• I continue using the CRT, $\begin{cases} 6x \equiv a^{121} \mod 4 \\ 6x \equiv a^{121} \mod 5 \end{cases}$ should verify – FranckN Dec 18 '13 at 16:54
• Anyway, $14x\equiv 3\pmod{15}$ immediately gives $x\equiv 12\pmod {15}$ so that we can take a few shortcuts. – Hagen von Eitzen Dec 18 '13 at 16:54
• oh, the $3$ es a $4$ sorry – FranckN Dec 18 '13 at 16:55