I'm having trouble solving this congruence: $$x^{114} \equiv 13 \pmod {29}.$$ I thought that it made sense to try to solve it using this idea: "Suppose you want to solve the congruence $ x^y \equiv a \pmod p$ (we will assume for the moment that $p$ is prime). Raise both sides to the power $z$ to obtain $x^{yz} \equiv a^z \pmod p$. Now if we can find a $z $ such that $yz \equiv 1 \pmod {p − 1}$ then the solution of the congruence will be $x \equiv a^z \pmod p$."

So I set $114 z \equiv 1 \pmod {28}$. However, $\gcd(114, 28) = 2$ and I can't solve for the inverse using the Euclidean algorithm. Does that statement that I quoted even come in handy anywhere?

Next I simplified $x^{114}$ to $x^2$ by Fermat's theorem.

I know that $x^2 \equiv 13 \pmod {29}$ has a solution because of the Legendre symbol: $$\left(\frac{13}{29}\right) \equiv 13^{14} \pmod {29} = 1$$

The only way I have learned to solve for square roots is when $p \equiv 3 \pmod 4$. Since this isn't the case, I'm at a loss as to how to find the square root. Any tips or hints?

  • 1
    $\begingroup$ Tonelli-Shanks or Cipolla algorithm in general. Here one just knows that $10^2 = 100 \equiv 13 \pmod{29}$, so $x \equiv \pm10 \pmod{29}$. $\endgroup$ Oct 7, 2013 at 20:46
  • $\begingroup$ What does that $=1$ mean near the end? $\endgroup$
    – dfeuer
    Oct 7, 2013 at 20:52
  • $\begingroup$ It's the Legendre symbol. If $(\frac ap) = +1$, then $x^2 = a (mod p)$ has a solution, and does not have a solution if = -1 $\endgroup$
    – Amber
    Oct 7, 2013 at 20:55
  • 1
    $\begingroup$ The notation looks very strange. If you mean $\left(\frac a p\right)=1$, why is that all mixed up with a congruence? $\endgroup$
    – dfeuer
    Oct 7, 2013 at 20:58
  • 1
    $\begingroup$ Once you have found a square root $x$ of $13$, you can use your idea to find the unique $y$ such that $y^{57}\equiv x\pmod{29}$. $\endgroup$ Oct 7, 2013 at 21:00

2 Answers 2


Here is my intuitive solution: $$x^{114} \equiv 13 \pmod {29}$$ As shown above by the Fermat Little Theorem, the congruence is simplified to $$x^{2} \equiv 13 \pmod {29}$$ Now we subtract $29$ from the right hand side of the congruence $$x^{2} \equiv -16 \pmod {29}$$ We can notice that $-16=4*(-4)$, so we can say $$4 \equiv 4 \pmod {29}$$ $$29-4 \equiv 25 \equiv -4 \pmod {29}$$ Now we multiply the last two congrunces $$100 \equiv -16 \equiv 13 \pmod {29}$$ 100 is a perfect square, thus the solution is $x=10$


Firstly, reduce the exponent immediately $\mod 28$ using Fermat's Theorem. So now you have to solve $x^2 = 13 \mod 29$ and since $13^{14} = 1 \mod 29$ you know there is a solution - actually there are two, namely $x$ and $29 - x$.

To find a solution in this simple case, just do a complete search up to $x = 14$. The result is $x = 10$. Anything else is a waste of time.

Now if you had to find $x$ such that $$ x^{3000000000000000000350} = 345679012320987652917 \mod 1000000000000000000117 $$ that would be a different matter. That's also a problem of the form "solve $x^2 = a \mod p$ and $p = 1 \mod 4$." In that case use the algorithm proposed by Daniel Fisher. It's built into Mathematica.


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.