So I'm having a bit of trouble proving the following theorem:
Suppose that $p$ is a prime, $k \in \mathbb{N}$ and $b \in \mathbb{Z}$. Show that the number of $k$th roots of $b$ modulo $p$ is either $0$ or $(k, p - 1)$ (note that $(\cdot,\cdot) \equiv \gcd(\cdot,\cdot)$).
Here is my attempt.
If there are $0$ roots then we are done.
Suppose now that the congruence $x^k \equiv b \mod{p}$ has a solution, say $x \equiv r \mod{p}$ for some $r \in \{0, 1, 2, \dots, p - 1\}$. We know that $p$ has exactly $\phi(p - 1)$ primitive roots and that $a^{v\phi(n) + 1} \equiv a \mod{p}$ for any $a \in \mathbb{Z}$. Now, if $(r,p) \ne 1$, then either $r = 1$ or $p \vert r$. If $r = 1$, then we must have $x^k \equiv 1 \mod{p}$. We know from a previous theorem that the order of any number modulo a prime must divide $p - 1$, so $(k,p - 1) = k$ (I'm not sure where to go from here). If $p \vert r$ , then $x \equiv 0 \mod{p} \Rightarrow x^k \equiv 0 \mod{p} \Rightarrow b \equiv 0 \mod{p}$ (again no idea if I'm headed in the right direction)...
Suppose that $(r,p) = 1$. Then $r^k \equiv b \mod{p} \Rightarrow r^{k\phi(p)} \equiv b^{\phi(p)} \Rightarrow b^{p - 1} \equiv 1 \mod{p}$. I know that there are $\phi(p - 1)$ such $b$ that satisfy this, but again, I have no idea where this is going..
I think it's likely that I'm just completely venturing out in the wrong direction here. Even a nudge in the right direction would be appreciated.
Answer
If $b \not \equiv 0\bmod p$ and $x^k \equiv b\bmod p$ has one solution $x=a$ then the other solutions are $x= a\zeta$ where $\zeta^k = 1$, which has $$ \# \{ \zeta \bmod p, \text{ord}(\zeta)\ |\ k\}=\# \{ \zeta \bmod p, \text{ord}(\zeta)\ |\ (k,p-1)\}= (k,p-1)$$ solutions, since $\mathbb{Z}/p \mathbb{Z}^\times$ is cyclic with $p-1$ elements so it contains an element $\mu$ of order $(k,p-1)$ and $\zeta^k=1 \implies \zeta = \mu^n$
No comments:
Post a Comment