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

  • $\begingroup$ 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... $\endgroup$ – 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}.$$

  • $\begingroup$ what can we say about the uniqueness of this solution? $\endgroup$ – DpS Dec 6 '16 at 16:12
  • $\begingroup$ It is unique modulo $143$. $\endgroup$ – Bernard Dec 6 '16 at 16:19
  • $\begingroup$ how do we get that? $\endgroup$ – DpS Dec 6 '16 at 16:21
  • $\begingroup$ 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$. $\endgroup$ – 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:

enter image description here

So yes, this checks out.

  • $\begingroup$ I know what to do after I find out x≡6(mod13) and x≡7(mod11), but don't understand how to get that... $\endgroup$ – 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?

  • $\begingroup$ yeah. tnx very much $\endgroup$ – 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.

  • $\begingroup$ Can you explain more how you got that?? $\endgroup$ – Talor T Jun 17 '16 at 23:55
  • $\begingroup$ 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. $\endgroup$ – SquirtleSquad Jun 17 '16 at 23:56
  • $\begingroup$ LOL... I need a formula since I do not have a calculator in the exam :( $\endgroup$ – Talor T Jun 17 '16 at 23:58
  • $\begingroup$ You don't need a calculator to compute 5th powers, and you can always reduce at every step, its fairly quick actually. $\endgroup$ – SquirtleSquad Jun 17 '16 at 23:59
  • $\begingroup$ 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. $\endgroup$ – SquirtleSquad Jun 18 '16 at 0:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.