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$

1 Answer 1

Reset to default
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$
4
  • $\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, 2014 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, 2014 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, 2014 at 21:46
  • $\begingroup$ Could you please tell me why $x$ must be of that form and not anything else? $\endgroup$
    – rah4927
    May 5, 2014 at 4:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .