how to solve $x^{113}\equiv 2 \pmod{143}$

Question

I need to solve $x^{113} \equiv 2 \pmod{143}$ $$143 = 13 \times 11$$

I know that it equals to $x^{113}\equiv 2 \pmod{13}$ and $x^{113}\equiv 2 \pmod{11}$

By Fermat I got

1) $x^{5} \equiv 2 \pmod{13}$

2) $x^{3} \equiv 2 \pmod{11}$

Now I'm stuck..

Answer 1

By the Chinese remainder theorem, you have to solve first $$\begin{cases}x^{113}\equiv2\mod13\\x^{113}\equiv2\mod11\end{cases}$$ Now Little Fermat says for any $x\not\equiv 0\mod 13\enspace(\text{resp. }11)$, one has $x^{12}\equiv 1\mod 13$, resp. $x^{10}\equiv 1\mod 11$. Hence the system of congruences is equivalent to $$\begin{cases}x^{113\bmod 12}\equiv x^5\equiv2\mod13,\\x^{113\bmod 10}\equiv x^3\equiv2\mod11. \end{cases}$$

Let's examine the different possibilities for $x$.

We can eliminate the values $0$ and $1$. Hence,

• modulo $13$, let's draw a table, using the fast exponentiation algorithm: $$\begin{matrix} x& \pm 2&\pm 3&\pm4 &\pm 5 & \pm 6\\ \hline x^2&4&-4&3&-1&-3\\ x^4&3&3&-4&1&-4\\ \hline x^5&\pm6&\pm6&\mp3&\pm5&\pm 2 \end{matrix}$$ Thus the solution is $\;\color{red}{x\equiv6\mod 13}$.
• modulo $11$, we have $$\begin{matrix} x& \pm 2&\pm 3&\pm4 &\pm 5\\ \hline x^2&4&-2&5&-1\\ \hline x^3&\mp3&\pm5&\mp 2&\mp5 \end{matrix}$$ Here the solution is $\;\color{red}{x\equiv-4\mod 11}$.

To solve this system of simultaneous congruences, we need a Bézout's relation between $13$ and $11$: $$6\cdot 11-5\cdot13=1.$$ The solutions of the system of congruences is $$x\equiv\color{red}{6}\cdot 6\cdot 11-(\color{red}{-4})\cdot5\cdot 13\equiv656\equiv \color{red}{84 \mod 143}.$$

Answer 2

Brute-force approach:

We want to find an $x$ such that $$x^{113} \equiv 2 \pmod{143}$$ We split $\mathbb{Z}_{143}$ into $\mathbb{Z}_{13} \times \mathbb{Z}_{11}$ since $13\cdot 11 = 143$ and $11,13$ are prime. Then, we compute the result of the congruences in $\pmod{13}$ and $\pmod{11}$, that is we solve

$$x^{113} \equiv 2 \pmod{13}$$ $$x^{113} \equiv 2 \pmod{11}$$

On which you already correctly applied Fermat, so you can reduce the exponent always $\pmod{p-1}$ with the prime modulus. Now you solve

$$x^{5} \equiv 2 \pmod{13}$$ $$x^{3} \equiv 2 \pmod{11}$$

By hand, to get

$$x \equiv 6 \pmod{13}$$ $$x \equiv 7 \pmod{11}$$

CRT goes like this: You know two congruences of $x$ in two moduli, that is

$$x \equiv a \pmod{p}$$

$$x \equiv b \pmod{q}$$

Where $p,q$ are relatively prime to each aother. From this, we can deduce the congruence of $x$ modulo $p\cdot q$ with

$$x \equiv a\cdot (q^{-1} \text{ mod }p)\cdot q + b\cdot (p^{-1} \text{ mod } q)\cdot p \pmod{pq} $$ (Follows from https://en.wikipedia.org/wiki/Chinese_remainder_theorem)

Through @Merlin's answer, we know that in this case

$$x \equiv 6 \pmod{13}$$ $$x \equiv 7 \pmod{11}$$

We calculate the needed inverses by using the extended eucledian algorithm (EEA):

$$13^{-1} \equiv 6 \pmod{11} $$ $$11^{-1} \equiv 6 \pmod{13} $$ We reconstruct $x$: \begin{align} x &\equiv a\cdot (q^{-1} \text{ mod }p)\cdot q + b\cdot (p^{-1} \text{ mod } q)\cdot p \pmod{pq}\\ &\equiv 6\cdot6\cdot11 + 7\cdot6\cdot 13 \equiv 942\pmod{11\cdot13} \\ &\equiv 84 \pmod{143} \end{align} We check that this is indeed a solution by direct computation with wolfram alpha:

So yes, this checks out.

Answer 3

$x^5 \equiv 2 (\mod13)$

$x^{12} \equiv 1(\mod 13)$ (Femat's little theorem.)

$5\cdot5\equiv 1 (\mod 12)\\ (2^5)^5 \equiv 2 (\mod 13)\\ (2^5) \equiv 6 (\mod 13)\\ x\equiv 6 (\mod 13)$

Now use the same logic mod 11

$x^{10} \equiv 1(\mod 11)\\ 3\cdot7 \equiv 1(\mod 10)\\ (2^7)^3 \equiv 2(\mod 11)\\ (2^7) \equiv 7(\mod 11)\\ 7^3 \equiv 2(\mod 11)\\ x\equiv 7(\mod 11)$

Can you get home from here?

Answer 4

The first congruence tells you $x \equiv 6 \pmod {13}$ and the second tells you $x \equiv 7 \pmod {11}$, now apply the Chinese remainder theorem to get your answer.