Hi everyone,

I'm trying to fill some gaps in my understanding of this Wikipedia page by proving some things that the author deemed obvious.

Higher residuosity problem - Wikipedia, the free encyclopedia

Not so sure in my skills in the area, so I need some help...

Theorem: If $\displaystyle Z_{p}^{*}$ is a multiplicative group of integers modulo $\displaystyle p$ for some prime $\displaystyle p$, and $\displaystyle d$ divides $\displaystyle p-1$ then the set of d-th powers of elements of $\displaystyle Z_{p}^{*}$ forms a subgroup of index $\displaystyle d$.

Facts on which the proof relies (and I've seen how they are proven):

1. $\displaystyle Z_{p}^{*}$ is cyclic

2. $\displaystyle Z_{p}^{*}$ is of order p-1.

Proof: Part 1: $\displaystyle H = \{m^d : m \in Z_{p}^{*}\}$ is a subgroup of $\displaystyle Z_{p}^{*}$

Claim 1 (closure): If $\displaystyle a \in H$ and $\displaystyle b \in H$ then $\displaystyle \exists m, n \in Z_{p}^{*}$ such that $\displaystyle m^d=a$ and $\displaystyle n^d=b$. Then $\displaystyle ab=(mn)^d$. But $\displaystyle mn\in Z_{p}^{*}$ so $\displaystyle ab=(mn)^d \in H$ by definition $\displaystyle H$.

Claim 2 (identity) $\displaystyle 1^d=1$ so $\displaystyle 1 \in H$ by definition of $\displaystyle H$.

Claim 3 (inverses) Let $\displaystyle a \in H$ then $\displaystyle \exists m \in Z_{p}^{*}$ such that $\displaystyle m^d=a$. But $\displaystyle m\in Z_{p}^{*}$, so $\displaystyle m^dm^{(p-1)-d}=1$, so $\displaystyle m^{(p-1)-d}$ is inverse of $\displaystyle m^d$. But $\displaystyle p-1$ is multiple of $\displaystyle d$, so $\displaystyle p-1-d$ is a multiple of $\displaystyle d$ too. Then it can be presented as $\displaystyle m^{xd}=(m^x)^d$ for some integer x, so $\displaystyle m^{(p-1)-d}$ is in $\displaystyle H$ by definition of $\displaystyle H$.

Proofs of claims 1-3 conclude the 1-st part of the proof.

Part 2: The index of $\displaystyle H$ is equal to $\displaystyle d$. Which is equivalent to saying that the order of H is $\displaystyle (p-1)/d$. I.e. $\displaystyle |Z_{p}^{*}| / |H| = d \Leftrightarrow (p-1) / |H| = d \Leftrightarrow |H| = (p-1)/d $.

Claim 1: $\displaystyle (p-1)/d$ divides $\displaystyle |H|$

Proof: $\displaystyle H$ is a sugroup of $\displaystyle Z_{p}^{*}$. So it is finite and cyclic. For each $\displaystyle m \in Z_{p}^{*}$ there is $\displaystyle a \in H$ such that $\displaystyle a = m^d$. So $\displaystyle (m^d)^{|H|}=1 \Leftrightarrow m^{d|H|}=1$. Therefore $\displaystyle p-1$ divides $\displaystyle d|H|$. But $\displaystyle d$ divides $\displaystyle p-1$ so $\displaystyle p-1$ can be written as $\displaystyle d \frac{p-1}{d}$ where $\displaystyle \frac{p-1}{d}$ is an integer. Then $\displaystyle d \frac{p-1}{d}$ divides $\displaystyle d|H|$ so $\displaystyle \frac{p-1}{d}$ divides $\displaystyle |H|$.

Claim 2: $\displaystyle |H|$ divides $\displaystyle (p-1)/d$. For each $\displaystyle a \in H$, exists $\displaystyle m\in Z_{p}^{*}$ such that $\displaystyle a=m^d$, but $\displaystyle m^{d\frac{p-1}{d}}=1$ so $\displaystyle a^{\frac{p-1}{d}}=1$. Therefore $\displaystyle |H|$ divides $\displaystyle (p-1)/d$.