1
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.