The system of Diophantine equations with same solution

Question

There is a system of Diophantine equations: \begin{equation*} \begin{cases} 368=x^7 (mod 407)\\ 389=x^{11}(mod 407) \end{cases} \end{equation*}

However, solving each of them by hand is quite a difficult task. The question is: how knowing both of the equations ease the task? How could they be solved manually in that case?

Answer 1

Here's one way.$$\begin{align} &x^{21}\equiv368^3\equiv103\pmod{407}\implies x^{22}\equiv103x\pmod{407}\\ &x^{22}\equiv389^2\equiv324\pmod{407}\end{align}$$

So we just have to solve $$103x\equiv324\pmod{407}$$

Answer 2

The Bezout equation $\gcd(7,11)=\underbrace{\color{#f84}{\bf 1} =\color{#0a0}{11\cdot 2} - \color{#c00}{7\cdot 3}}\,$ yields exponent $\color{#f84}{\bf 1}$ on $\,x\,$ as follows

$$\qquad\qquad\qquad\qquad\ \ x^{\Large\color{#f84}{\bf 1}}\equiv\, \dfrac{(x^{\Large \color{#0a0}{11}})^{\Large \color{#0a0}2}}{(x^{\Large \color{#c00}{7}})^{\Large \color{#c00}3}}\equiv \dfrac{389^{\large 2}}{368^{\large 3}}\equiv \dfrac{-83}{103}\equiv 15\!\pmod{\!407} $$

i.e. $\ x\equiv -83\cdot 103^{-1}.\,$ The inverse can be computed by the Extended Euclidean algorithm.

Notice that our inferences are unidirectional, i.e. any solution of the system must satisfy the above. They do not imply that $\,x\equiv 15\,$ is a solution, so you need to check (or prove) that it is.

Answer 3

To expand on my comment; because $407=11\times37$, by the Chinese remainder theorem the system is equivelent to \begin{eqnarray} x^7&\equiv&368\equiv5&\pmod{11},\tag{1}\\ x^7&\equiv&368\equiv35&\pmod{37},\tag{2}\\ x^{11}&\equiv&389\equiv4&\pmod{11},\tag{3}\\ x^{11}&\equiv&389\equiv19&\pmod{37}.\tag{4} \end{eqnarray} In particular $x\not\equiv0\pmod{11}$ and $x\not\equiv0\pmod{37}$, so by Fermat's little theorem $$x^{10}\equiv1\pmod{11} \qquad\text{ and }\qquad x^{36}\equiv1\pmod{37}.$$ Then congruence $(3)$ immediately shows that $x\equiv4\pmod{11}$, and congruences $(2)$ and $(3)$ together show that $x^{18}\equiv-1\pmod{37}$. Then a bit of fiddling around yields the identity $$x\equiv x^{37} \equiv-x^{37+18} \equiv-x^{11\times 5} \equiv -19^5\pmod{37},$$ and a quick computation then shows that $x\equiv15\pmod{37}$, so by the Chinese remainder theorem the solution to the system is $x\equiv15\pmod{407}$.