10
$\begingroup$

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?

$\endgroup$
11
  • 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$ Commented Oct 7, 2013 at 20:46
  • $\begingroup$ What does that $=1$ mean near the end? $\endgroup$
    – dfeuer
    Commented 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
    Commented 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
    Commented 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$ Commented Oct 7, 2013 at 21:00

2 Answers 2

2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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