Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
1  
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}$. – Daniel Fischer Oct 7 '13 at 20:46
    
What does that $=1$ mean near the end? – dfeuer Oct 7 '13 at 20:52
    
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 – Amber Oct 7 '13 at 20:55
1  
The notation looks very strange. If you mean $\left(\frac a p\right)=1$, why is that all mixed up with a congruence? – dfeuer Oct 7 '13 at 20:58
1  
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}$. – André Nicolas Oct 7 '13 at 21:00

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$

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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