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

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..

• If $x^5 \equiv 2 \mod 13$, then $x^{5+(13-1)} \equiv 2 \mod 13$, and $x^{5+2(13-1)} \equiv 2 \mod 13$, etc... – JasonM Jun 17 '16 at 23:49

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}.$$

• what can we say about the uniqueness of this solution? – DpS Dec 6 '16 at 16:12
• It is unique modulo $143$. – Bernard Dec 6 '16 at 16:19
• how do we get that? – DpS Dec 6 '16 at 16:21
• It's the Chinese remainder theorem: $\mathbf Z/11\mathbf Z\times \mathbf Z/13\mathbf Z\simeq \mathbf Z/11\cdot 13\mathbf Z$. – Bernard Dec 6 '16 at 16:27

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.

• I know what to do after I find out x≡6(mod13) and x≡7(mod11), but don't understand how to get that... – Talor T Jun 18 '16 at 0:20

$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?

• yeah. tnx very much – Talor T Jun 20 '16 at 19:46

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.

• Can you explain more how you got that?? – Talor T Jun 17 '16 at 23:55
• Honestly, just by brute force, start at 2 and take 5-th powers, reduce them mod 13 until you get 2. Then repeat for cubes mod 11. – SquirtleSquad Jun 17 '16 at 23:56
• LOL... I need a formula since I do not have a calculator in the exam :( – Talor T Jun 17 '16 at 23:58
• You don't need a calculator to compute 5th powers, and you can always reduce at every step, its fairly quick actually. – SquirtleSquad Jun 17 '16 at 23:59
• For example, with 6 mod 13, its powers are 6->10->8->9->2, theres no need to ever work with a number greater than the modulus-1 squared. – SquirtleSquad Jun 18 '16 at 0:06