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

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?

• $(x^5)^{17}\equiv x^{85}\equiv (x^{28})^3x\equiv x$, , so if $x^5\equiv8\bmod29$, then $x\equiv8^{17}\equiv 2^{51}=2^{28}2^{23}\equiv2^{23}$ Dec 11, 2020 at 3:54
• $2^7\equiv12\bmod29$ Dec 11, 2020 at 4:00

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}$$.

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

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

• Note: the equivalence in the first displayed equation is by mod order reduction. Apr 8, 2022 at 1:45
• For me this is a very confusing answer. The exponential equation modulo 29 can be transformed in a linear equation modulo 28. and this can be split in an equation modulo 4 and an equation modulo 7 which can easily be solved. Apr 8, 2022 at 4:16

$$(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$$.

• I'm sure I'm overlooking something simple, but it's not immediately clear to me why $x^4 \equiv 4 \mod 29$ being soluble implies that $x^2 \equiv 2 \mod 29$ is soluble? I can see that the converse is obvious. It obviously feels intuitively true but I'm thinking about how to actually prove it from first principles and I'm struggling
– cb7
Dec 11, 2020 at 5:10
• I think you're right and I was wrong Dec 11, 2020 at 5:37
• How’s the argument now? Dec 11, 2020 at 5:59