I need a little help with the following question:
If $a$ is an integer such as $71\nmid a$ and $x^7\equiv a\pmod {71}$ has an integer solution. How many positive integer solution there is for this equation that lower than 71?
All I understand is that $71$ is prime.
And that because $71\nmid a$ then $\gcd (a,71) = 1$ so we know there is $s,t\in \mathbb Z$ such as $sa+71t=1$ then $71t=1-sa$ then $71 \mid 1-sa$ then $sa \equiv 1\pmod {71}$.
If $c$ is a solution then $c^7\equiv a\pmod {71}$ then $71\mid c^7-a.$
Thanks in advance
Best Answer
The multiplicative group mod a prime $p$ is cyclic. A generator of this group is called a primitive root mod $p$. If $b$ is a primitive root, it means for each $x \in \{1,\ldots, p-1\}$ we can write $x \equiv b^j \mod p$ for some unique $j \in \{1,\ldots, p-1\}$. $b$ has order $p-1 \mod p$. It turns out, for example, that $11$ is a primitive root mod $71$, but you don't need to know that for this question, you only need to know the theorem that a primitive root exists for each prime.
If $d$ is any divisor of $p-1$ and $x^d \equiv 1 \mod p$ where $x \equiv b^j \mod p$, that says $b^{jd} \equiv 1 \mod p$, so $jd$ must be divisible by $p-1$. So, the number of such $x$ is the same as the number of $j \in \{1, \ldots, p-1\}$ such that $p-1 \mid jd$. So in your case, how many members $j$ of $\{1,\ldots, 70\}$ are there such that $7j$ is divisible by $70$?