Monday, November 6, 2017

modular arithmetic - How to solve congruence $x^y = a pmod p$?

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?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...