Exercise 3.2.26* (Characterization of $k$th power residue modulo $p$)

Proof. Let $G={𝔽}_p^{\text{∗}}={(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}}$ be the multiplicative group of the field ${𝔽}_p$, and let $H=⟨a⟩=\{1,a,a^2,\dots ,a^{k-1}\}$ be the subgroup of $G$ generated by $a\in G$. Consider the quotient group $\bar{G}=G∕H$, whose elements are the classes $\mathit{xH},x\in G$. Then

(By Lagrange’s theorem (Theorem 2.49), the order of $\mathit{bH}$ in $\bar{G}$ is a divisor of the order of the group $\bar{G}$, thus $b^{(p-1)∕k}H={(\mathit{bH})}^{(p-1)∕k}=H$, which gives

so that there is some integer $l$ such that $b^{(p-1)∕k}=a^l$, but we will not use directly this result.)

Now let $𝒯$ be a transversal of $H$. Then $𝒯$ is a complete system of representatives of the classes of $G∕H$, meaning that

• For every $C\in G∕H$, there is a $t\in 𝒯$ such that $C=\mathit{tH}$.

• The element $t\in 𝒯$ such that $C=\mathit{tH}$ is unique: if $t,t^{\prime }$ are in $𝒯$, then

  $$\begin{array}{lll}\hfill \mathit{tH}=t^{\prime }H\Rightarrow t=t^{\prime }.& & \hfill \text{(1)}\end{array}$$

Indeed, for every class $C\in G∕H$, there is some $x\in G$ such that $C=\mathit{xH}$, and by definition of a transversal, $x=t{a}^i$ for some $t\in 𝒯$ and $i\in [[0,k-1]]$. Thus $C=\mathit{xH}=t{a}^{i}H=\mathit{tH}$, because $a^i\in H$. Moreover, if $\mathit{tH}=t^{\prime }H$, where $t,t^{\prime }\in H$, then $t{a}^i=t^{\prime }{a}^j$ for some integers $i,j\in [[0,k-1]]$. The definition of a transversal implies that $t=t^{\prime }$.

Conversely, every complete system $𝒯$ of representatives of the classes of $G∕H$ is a transversal: for every $x\in G$, there is a some $t\in 𝒯$ such that $\mathit{xH}=\mathit{tH}$, thus $x\in \mathit{tH}$, and so $x=t{a}^i,i\in [[0,k-1]]$. Moreover, if $t{a}^i=t^{\prime }{a}^j$, where $t,t^{\prime }\in 𝒯,i,j\in [[0,k-1]]$, then $\mathit{tH}=t^{\prime }H$, thus $t=t^{\prime }$ by (1). Therefore $a^i=a^j$, where $i,j\in [[0,k-1]]$. Since $k$ is the order of $a$, we obtain $i=j$. In particular, this shows that transversals of $H$ exist: it suffices to choose a representative $t$ in each class of $G∕H$ to build a transversal.

This shows that the numbers of elements of $𝒯$ is $n=|\bar{G}|=(p-1)∕k$. Write $t_1,t_2,\dots ,t_n$ the elements of $𝒯$, where $n=(p-1)∕k$. Then $G∕H=\{t_{1}H,t_{2}H,\dots ,t_{n}H\}$. By definition of $I$,

for some elements $t_1^{\prime },t_2^{\prime },\dots ,t_n^{\prime }$ in $𝒯$.

Note that

is bijective ( $\phi$ is the multiplication by the element $\mathit{bH}\in G∕H$). Therefore $\phi$ permutes the classes $t_{1}H,t_{2}H,\dots ,t_{n}H$, so that there is a permutation $\sigma$ in the symmetric group $S_n$ such that $\phi (t_{j}H)=t_{\sigma (j)}H$, $j=1,2,\dots ,n$. This implies $b{t}_{j}H=t_{{\sigma }_j}(H)$, and also $t_j^{\prime }H=a^{I(b{t}_j)}{t}_j^{\prime }H=t_{\sigma (j)}H$. By (1), we obtain $t_j^{\prime }=t_{\sigma (j)}$. We can rewrite the preceding equalities under the form

The product of all the equalities gives

Since $\sigma$ is a permutation, ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{j=1}^n{t}_j={\prod }_{j=1}^n{t}_{\sigma (j)}$. The simplification by this element in the group $G$ gives $b^n={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{j=1}^n{a}^{I(b{t}_j)}$, that is

By Theorem 2.37, $b$ is a $k$th power in $G$ if and only if $b^{(p-1)∕k}=1$. By equation (2), this is equivalent to

Since the order of $a$ is $k$, this is equivalent to

So $b$ is a $k$th power if and only if $\underset{t\in 𝒯}{\sum <!--\; FUNCTION\; APPLICATION\; -->}I(\mathit{bt})\equiv 0(modk)$. □