How could I go about solving $y^{20} \equiv 13 \pmod {17}$ 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 https://docs.google.com/viewer?a=v&q=cache:zW44-UarVWcJ:https://www2.bc.edu/christian-zorn/course_stuff/exam_2_mt430_v1_solns.pdf+&hl=en&gl=us&pid=bl&srcid=ADGEESjMp-OcTt9dpZ1Y4ZeWf8QV4itnejB01z_rrVeTDC0MWw7Mirb9s4g2zmyz3Lxk4HMDQhYNk8l_a7aLZc-iSLDD_Fmep2XJklPeJ8HgNDpl8aOaxmSSZVJzBmsmptnB9JrGjR3p&sig=AHIEtbR3TLbTnsEDBh8D4T6rVLOd1TmRWg but am not sure how exactly to do so
 A: 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.$
A: 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
A: 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$
