1
$\begingroup$

I have a workbook question that doesn't have any example solution, that is as follows:

Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$

Now I can see $\phi(11)=10$ and $2$ has order $10$ so $2$ is the primitive root $\pmod{11}$

I can see aswell that $2^4 \equiv 5 \pmod{11}$, so I can show $x^7 = 2^4 \pmod{11}$, must I compute the powers of all the numbers until I find which yields $5 \pmod{11}$, how do I use primitive roots to solve the prolem?

$\endgroup$
3
$\begingroup$

Let $x=2^k$. Then solve for $k$.

ADD We have $2^{7k}=2^4\mod 11$, so that $2^{7k-4}=0\mod 11$. Since the order of $2$ modulo $11$ is $10$, $7k=4\mod 10$. Hence $k=3\cdot 4=12=2\mod 10$. It follows $x=4$.

$\endgroup$
  • $\begingroup$ So I have $(2^k)^7=2^{7k} = 2^4$ then using a theorem result, $7k=4 \pmod{10}$, $7$ has inverse $3$, so $k = 7*3*4$, so $x^7 = x^{84}$? - $\endgroup$ – Display Name May 4 '14 at 21:27
  • $\begingroup$ Edit was too late above: " So I have $(2^k)^7=2^{7k} = 2^4$ then using a theorem result, $7k=4 \pmod{10}$, $7$ has inverse $3$, so $k = 7*3*4$, so $2^7 \cong 5 \mod{11}, 2^{84} = x^7, x = 2^{12}$?" $\endgroup$ – Display Name May 4 '14 at 21:35
  • $\begingroup$ My remaining query before accepting your answer, Is this the correct number to obtain using the method(as in, should/can I minimise it somehow? $\endgroup$ – Display Name May 4 '14 at 21:46
  • $\begingroup$ Could you please tell me why $x$ must be of that form and not anything else? $\endgroup$ – rah4927 May 5 '14 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.