# A solution to $y^5 \equiv 2\pmod{251}$

I need to show that the following equation has a solution. (I am not asked for the answer, which I know by Mathematica to be $y=43$. )

$y^5 \equiv 2 \pmod{251}.$

I know that the order of 2 is 50, so $2^{50} \equiv 1$. Could we raise both sides of the equation to the power of 50, which would give the trivial result of $y^{250} \equiv 1$? My first approach was to consider $(y^5)^k=y^{5k}=yy^{5k-1}$ and then finding the value of $k$ such that $5k \equiv 1 (\bmod 250)$, however this doesn't work as $\gcd(5,250) \neq 1$.

-
There is not just one answer but 5 answers! –  fretty Mar 7 '12 at 8:30
You were almost there. The non-zero elements are a cyclic group of order 250, right? Since $2$ has order $50$, you're simply asking if an $x$ satisfying $50x \equiv 0 \pmod {250}$ is a multiple of $5$. (this is essentially what steve's answer is doing) –  Hurkyl Mar 7 '12 at 9:14

Let $x$ be a primitive root modulo $251$, so that every non-zero residue modulo $251$ is a power of $x$ and if $x^m=1$ mod $251$ then $m$ is divisible by $250$. Write $2=x^k$ for some integer $k$ and use the fact that $x^{50k}=2^{50}=1$ mod $251$ to obtain that $k$ is divisible by $5$. Thus $2=x^{5l}=(x^l)^5$ mod $251$ for some integer $l$.

-
@Ross Millikan, Well, $x$ being a primitive root means, by definition that its order is $250$. Now if $x^m=1$ then the order, $250$, of $x$ has to divide $m$, no? –  S123 Mar 5 '12 at 22:51
Huh. I could have sworn that comment was a reply to someone. –  S123 Mar 5 '12 at 23:20
There was a comment, indeed, which was deleted by its owner. –  Mariano Suárez-Alvarez Mar 7 '12 at 9:20

A probabilistic root finding algorithm for finite fields can do the job. The following is described in the book Rudolf Lidl & Harrald Niederreiter, Finite Fields, Cambridge University Press, 1997, 168pp all the numbers of $F_{251}$ except $0$ are roots of $x^{250}-1$ and therefore roots of either $x^{125}-1$ or $x^{125}+1$. to find a root from a polynomial $f(x)=x^5-2$, take a randomly selected number from ${1,...,250}$. I will take the number $1$. Then calculate $$gcd(f(x-1),x^{125}-1)=x^3-79*x^2+4*x-89$$ $$gcd(f(x-1),x^{125}+1)=x^2+74*x+79$$ Repeat the process until you have only linear factors. For these polynomials you get the factors $$(x-108)*(x-91)*(x+120)$$ for the second you get the factors $$(x-44)*(x+118)$$ Therefore $$f(x-1)=(x-108)*(x-91)*(x+120)*(x-44)*(x+118)$$. Now substitute $x+1$ for $x$ to get $$f(x)=(x-107)*(x-90)*(x-43)*(x+119)*(x+121)$$ and the zeroes $$197,90,43,132,130$$ for $$x^5-2=0$$

-
+1 Nice in a way. Do observe that for the purposes of answering the present question (=deduce the existence of a solution) it suffices to calculate $\gcd(x^5-2,x^{125}-1)$, and observe that is not a constant. –  Jyrki Lahtonen Mar 7 '12 at 8:09

One can find the roots of your polynomal by checking every number from ${1,...,250}$ and use some tricks like those @Steve showed to save some labour. But calculating the roots of a polynomial $\mod p$ for a large prime is not a trivial task and I think you will not have success with your approach. But there are efficient algorithms. Two of them based on facts from the theory of finite groups and finite fields are described in

-

For these special numbers it is possible to calculate the roots using pencil and paper. I give you hints because I assume you want to do the calculations by yourselve.

Observe that there is a relation between the base $2$, a 5th power and the modulus $251$:

$$3^5+2^3=251$$

Use this to construct a solution of

$$x^5 \equiv 2 \mod 251$$

How many 5th roots of $2$ are there? Construct the others from the one you have found.

-