1
$\begingroup$

Given the equation:

$$x^e\equiv c \pmod p$$

where $p$ is prime number, $c$ is positive integer and $e$ is positive integer and $\gcd(e, p-1) = 1$. Explain how would you solve given equation.


Also, using that explanation solve next equation:

$$x^{77} \equiv 2 \pmod{246}$$

I know that I need to use Chinese reminders theorem but I am not sure how... Please can you provide some explanation how to solve this.

$\endgroup$
1
  • $\begingroup$ 246 is not prime. You can use the chinese remainder theorem to split it into prime factors before you can apply the answer given by Watson, but I think his answer may work if there exists a solution anyways. $\endgroup$ Commented Sep 1, 2016 at 20:16

2 Answers 2

3
$\begingroup$

By Bézout's theorem, there are integers $a,b$ such that $ae+b(p-1)=1$. Therefore, $$x = x^{ae+b(p-1)}\;\; \equiv c^a \cdot (x^{p-1})^b \equiv c^a \pmod p.$$


For your specific question, you have $$\begin{cases} x^{77} \equiv x \equiv 2 \equiv 0 \pmod 2\\ x^{77} \equiv x \equiv 2 \pmod 3\\ x^{77} \equiv 2 \pmod{41}\\ \end{cases}$$ The last equation becomes, because of the Bézout's identity $-25 \cdot 40 + 13 \cdot 77 = 1$, $$x \equiv 2^{13} \equiv 33 \pmod{41}$$ Then using the CRT you get $x \equiv 74 \pmod{246}$.

$\endgroup$
9
  • $\begingroup$ In fact the computations which you omitted (inverse computation, and CRT lifting) can be done completely with simple mental arithmetic if you know the shortcuts - see my answer. $\endgroup$ Commented Sep 1, 2016 at 23:20
  • $\begingroup$ If I understood, there are three equations mod 2, 3 and 41. You have transformed only the last one, and used CRT for which equations? $\endgroup$
    – clzola
    Commented Sep 4, 2016 at 11:40
  • $\begingroup$ @clzola: Yes. I only needed to transform the last one because for the first one I used $y^{77} \equiv 0 \pmod 2 \implies y \equiv 0$, and for the second one $y^2 \equiv 1 \pmod 3$ if $y≠0$. $\tag*{}$ I have the system $$\begin{cases} x \equiv 0 \pmod 2\\ x \equiv 2 \pmod 3\\ x \equiv 33 \pmod{41}\\ \end{cases}$$ so I used the CRT to solve it. $\endgroup$
    – Watson
    Commented Sep 4, 2016 at 11:50
  • $\begingroup$ @clzola: When you have $am+bn=1$, with $m,n$ coprime, then the system $$\begin{cases} x \equiv r \pmod n\\ x \equiv s \pmod m\\ \end{cases},$$ has the solution $x \equiv r(1-bn) + s(1-am) \pmod{nm}$. $\endgroup$
    – Watson
    Commented Sep 4, 2016 at 11:53
  • $\begingroup$ @Watson, thank you! Does this equation has some name, so I can look on google for more examples. I have only this one, but would be great if I could find more... $\endgroup$
    – clzola
    Commented Sep 4, 2016 at 11:59
1
$\begingroup$

Yes, CRT works. $\ $ Easily $\,x\equiv 2\pmod{6}\,$ and $\ x\!\pmod{41}\,$ can be computed mentally:

${\rm mod}\ 40\!:\,\ \color{#c00}{\dfrac{1}{77}}\equiv \dfrac{-39}{-3}\equiv \color{#c00}{13},\ $ so $\,\ {\rm mod}\ \color{#0a0}{41\!:\ \, x}\equiv 2^{\color{#c00}{\large 1/77}}\!\equiv 2^{\color{#c00}{\large 13}}\!\equiv 2^{\large 3}(2^{\large 5})^{\large 2}\equiv 8(-9)^{\large 2}\equiv \color{#0a0}{-8}$

${\rm mod}\ 6\!:\ 2\equiv x\equiv \color{#0a0}{-8+41k}\equiv -8\!-\!k\!\iff\! k\equiv 2,\, $ so $\,x\equiv -8+41\cdot 2\equiv 74\pmod{\!6\cdot 41}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .