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 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 .