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 is a multiplicative group of integers modulo for some prime , and divides then the set of d-th powers of elements of forms a subgroup of index .
Facts on which the proof relies (and I've seen how they are proven):
1. is cyclic
2. is of order p-1.
Proof: Part 1: is a subgroup of
Claim 1 (closure): If and then such that and . Then . But so by definition .
Claim 2 (identity) so by definition of .
Claim 3 (inverses) Let then such that . But , so , so is inverse of . But is multiple of , so is a multiple of too. Then it can be presented as for some integer x, so is in by definition of .
Proofs of claims 1-3 conclude the 1-st part of the proof.
Part 2: The index of is equal to . Which is equivalent to saying that the order of H is . I.e. .
Claim 1: divides
Proof: is a sugroup of . So it is finite and cyclic. For each there is such that . So . Therefore divides . But divides so can be written as where is an integer. Then divides so divides .
Claim 2: divides . For each , exists such that , but so . Therefore divides .