Solving $x^d \equiv a \pmod{29}$ using primitive roots

Question

Can anyone please detail the general approach to questions of the form $x^d \equiv a \pmod{29}$? For example, Wolfram Alpha states that $x^5 \equiv 8 \pmod{29}$ has one solution, $x^4 \equiv 4 \pmod{29}$ has no solution, and $x^7 \equiv 12 \pmod{29}$ has many solutions, but I have no idea how I'd go about proving that no solutions exist, or that any solutions I find are comprehensive.

I know that $2$ is a primitive root $\bmod 29$, so $2^{28} \equiv 1 \pmod{29}$. For the first one I can manipulate to get $(2^{23})^5 \equiv 8 \pmod{29}$ to give $x \equiv 2^{23} \equiv 10 \pmod{29}$ as a solution, but this doesn't prove that no other solutions exist, does it? Also, I don't know how this approach would work with the third problem because $12$ cannot be written $2^n$.

Furthermore, I'm unsure of the general technique to show that the second is not soluble?

Answer 1

Since $2$ is a primitive root modulo $29$, its multiplicative order is $28$, which means

$$2^y \equiv 2^z \pmod{29} \iff y \equiv z \pmod{28} \tag{1}\label{eq1A}$$

One way to solve your congruence equations is to first express the right hand sides as a congruent power of $2$. The first $2$ examples are quite easy. With the third one, i.e.,

$$x^7 \equiv 12 \pmod{29} \tag{2}\label{eq2A}$$

note $12 \equiv 3(4) \equiv (32)(4) \equiv 2^7 \pmod{29}$ (as J. W. Tanner's question comment states). Next, since $2$ is a primitive root and $x \not\equiv 0 \pmod{29}$, then there's an integer $1 \le a \le 28$ such that $x \equiv 2^a \pmod{29}$. Thus, \eqref{eq2A} becomes

$$\left(2^{a}\right)^7 \equiv 2^7 \pmod{29} \implies 2^{7a} \equiv 2^7 \pmod{29} \tag{3}\label{eq3A}$$

Using \eqref{eq1A}, this gives

$$7a \equiv 7 \pmod{28} \implies a \equiv 1 \pmod{4} \tag{4}\label{eq4A}$$

This gives multiple answers of $x \equiv 2^{4b + 1} \pmod{29}$ for $0 \le b \le 6$, i.e., $x \equiv 2, 3, 19, 14, 21, 17, 11 \pmod{29}$.

Next, with your second example,

$$x^5 \equiv 8 \equiv 2^3 \pmod{29} \tag{5}\label{eq5A}$$

as done before, let $x \equiv 2^a \pmod{29}$ to get

$$2^{5a} \equiv 2^3 \pmod{29} \implies 5a \equiv 3 \pmod{28} \implies a \equiv 23 \pmod{28} \tag{6}\label{eq6A}$$

Thus, $x \equiv 2^{23} \pmod{29}$ is the answer, as J. W. Tanner's question comment also indicates.

With your final example of

$$x^4 \equiv 4 \equiv 2^2 \pmod{29} \implies x^2 \equiv \pm 2 \tag{7}\label{eq7A}$$

note $2$ is not a quadratic root modulo $29$ (which requires, as shown in this table that $p \equiv 1, 7 \pmod{8}$ but $29 \equiv 5 \pmod{8}$), and also $-2$ is not a quadratic residue (since that requires $p \equiv 1, 3 \pmod{8}$). In addition, using the method I show above, gives

$$2^{4a} \equiv 2^2 \pmod{29} \implies 4a \equiv 2 \pmod{28} \implies 2a \equiv 1 \pmod{14} \tag{8}\label{eq8A}$$

However, it's not possible to have an even value be equivalent to an odd value with an even modulo (e.g., since it would require $14 \mid 2a - 1$), so there are no solutions.

Answer 2

$(x^5)^{17}\equiv x^{85}\equiv (x^{28})^3x\equiv x\bmod 29$,

so if $x^5\equiv8\bmod29$, then $x\equiv8^{17}=2^{51}=2^{28}2^{23}\equiv2^{23}\equiv10\bmod29$.

If $x^4\equiv4=2^2\bmod29$ had solutions, then $1\equiv x^{28}\equiv (x^4)^7\equiv(2^2)^7=2^{14}\bmod29$, so $2$ would not be a primitive root.

$2^7\equiv12\bmod29$, so if $x^7\equiv12\bmod29$, then $x^7\equiv2^7\bmod29$,

so $x\equiv2a\bmod29$, where $a^7\equiv1\bmod29$.

$a^7\equiv1\bmod29$ when $a\equiv2^0, 2^4, 2^8, 2^{12}, 2^{16}, 2^{20}, $ or $2^{24}$; i.e., $a\equiv1, 16, 24, 7, 25, 23, $ or $20$;

so $x\equiv2, 3, 19, 14, 21, 17, $ or $11\bmod29$.