Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

How could I go about solving $y^{20} \equiv 13 \pmod {17}$

I know that phi(17) = 16. and gcd(20,16) = 4 ; 13^{16/4} ≡ 1 mod 17 So we must have 4 solutions. I am just learning about orders so I am thinking order d=1,2,4,8,16?

I know I can most likely use that table of indices like the one on page 5 of but am not sure how exactly to do so

share|cite|improve this question
up vote 0 down vote accepted

As $\phi(17)=16,3^4=81\equiv13\equiv -4\pmod{17}\implies 3^8\equiv(-4)^2=16\equiv-1\implies 3$ is a primitive root of $17$

Now, using Discrete Logarithm, $20ind_3y\equiv ind_3{13}\pmod {\phi(17)}$

$\implies 20ind_3y\equiv 4\pmod {16}$ as $3^4\equiv13\pmod{17}\iff ind_3{13}=4$

$\implies 5ind_3y\equiv 1\pmod 4$

$\implies ind_3y\equiv 1\pmod 4=4z+1$ where $z$ is any integer.

So, $y\equiv3^{4z+1}\pmod{17}$

Now, as the index of any number co-prime to $n$ lies $\in[0,\phi(n)];$ $0\le 4z+1\le \phi(17)=16\implies 0\le z\le 3$

share|cite|improve this answer
how did you get rid of the 5 in $5ind_3y≡1(mod4)$ – walt23 Feb 28 '13 at 16:40
@walt23, As $5\equiv1\pmod 4\iff 5^{-1}\equiv1\pmod 4$ – lab bhattacharjee Feb 28 '13 at 16:42

Hint $\ $ By little Fermat, $\rm\: mod\ 17\!:\ y\not\equiv 0\:\Rightarrow\:y^{16}\!\equiv 1,\:$ so $\rm\:y^4\! \equiv y^{20}\!\equiv 13\equiv 8^2\Rightarrow\: y^2\!\equiv \pm 8.\:$ Noticing $\rm\: 8\equiv 5^2,\:$ and $\rm\:-8\equiv 3^2,\:$ we concude $\rm\ y\equiv \pm3,\ \pm 5.$

share|cite|improve this answer

Hint: Certainly $y\not\equiv0$. Since $y^{20}\equiv 13$, therefore $y^{60}\equiv13^3\equiv4$ Thus $(y^4)^{15}\equiv 4$. By FLT, $(y^4)^{15}\equiv y^{-4}$ (because $\phi(17)=16$). Thus, $y^4\equiv (y^2)^2\equiv13^{-1}$. Now you can use quadratic recopricity to check if there are solutions

share|cite|improve this answer

Your Answer


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.