F ind the seven solutions to $x^{7} \equiv 1 \pmod{29}$

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?

• What about $2^{2\cdot 4}, 2^{3\cdot 4}, \dotsc$? Oct 7 '13 at 15:30
• $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. Oct 7 '13 at 16:05

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

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