Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.