# 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

-

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$

-
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.$

-

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

-