5
$\begingroup$

Use the fact that $2$ is a primitive root modulo 29 to find the seven solutions to $x^{7} \equiv 1 \pmod{29}$

As $2$ is primitive root modulo $29$ then $$2^{28} \equiv 1 \pmod{29} $$ $$2^{4*7} \equiv 1 \pmod{29} $$ $$16^{7} \equiv 1 \pmod{29} $$ where 16 is a solution to the equation. From this solution as I can get 6 missing solutions?

$\endgroup$
2
  • 2
    $\begingroup$ What about $2^{2\cdot 4}, 2^{3\cdot 4}, \dotsc$? $\endgroup$ Oct 7 '13 at 15:30
  • 1
    $\begingroup$ $1=16^0,16^1,16^2,16^3,16^4,16^5,16^6$. Check that they are distinct (using the fact that $2$ is a primitive root), and since you have a polynomial of degree $7$ over a field, you have at most $7$ solutions, so we get a complete set. $\endgroup$ Oct 7 '13 at 16:05
5
$\begingroup$

We know that $2^{28} \equiv 1 \bmod 29$, i.e. $16^7 \equiv 1 \bmod 29$. However we can also conclude from this that:

$16^{14},16^{21},16^{28},16^{35},16^{42},16^{49} \equiv 1 \bmod 29$.

So $16^2, 16^3, 16^4, 16^5, 16^6, 16^7$ are the other $6$ solutions.


Alternatively: we know every $x\in\mathbb{Z}/29\mathbb{Z}$ can be written as $x=2^k$ for some $k$.

To satisfy $x^7 \equiv 1 \bmod 29$ we require $2^{7k} \equiv 1 \bmod 29$. But since $2$ is a primitive root mod $29$ this means that $7k \equiv 0 \bmod 28$, i.e. $k \equiv 0 \bmod 4$ so we may take $k=0,4,8,12,16,20,24$ (after this the powers of $2$ repeat).

$\endgroup$
0
$\begingroup$

Using Discrete Logarithm wrt $2$,

we have $$7\text{ind}_2x\equiv0\pmod{28}$$

Using Linear congruence theorem (Proof), the equation is solvable as $0$ is divisible by $(7,28)=7$ and has exactly $7$ solutions namely $0+k\frac{28}7=4k$ where integer $k\in[0,7-1=6]$

So, the $7$ solutions of $x^7\equiv1\pmod{29}$ are $2^{4k}=16^k$ where integer $k\in[0,6]$

$\endgroup$

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.