# Thread: Need someone to check a proof for weak points

1. ## Need someone to check a proof for weak points

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

2. ## Re: Need someone to check a proof for weak points

a few remarks:

the fact that ab = (md)(nd) = (mn)d relies on the fact that multiplication modulo p is commutative.

claim 2) and claim 3) of part 1) are superfluous, Zp* is finite, so closure suffices.

for part 2) claim 1):

i think you want to use a specific a, here; namely, let m be a generator for Zp*, so that |m| = p-1. then it follows from a result on cyclic groups that:

a = md has order (p-1)/d. thus <a>, which is a subgroup of H, has order (p-1)/d, so (p-1)/d divides |H|.

in particular, i found this statement:

"....md|H| =1, Therefore, p-1 divides d|H|..."

hard to follow, unless we know something about m (it is trivially true that for any group G, g|G| = e, but that reveals very little about the order of g). i think we need to know that |m| = p-1, for this to tell us that p-1 divides d|H|.

claim 2): again, i think you need to pick an a in H, with |a| = |H|. we can do this, because H is a subgroup of a cyclic group, so is itself cyclic. just knowing that for every g in G, gk = e, doesn't tell you k = |G| (for example, in V, the klein 4-group, it's true that g2 = e, for every element g, but |V| = 4, not 2).

you *can* however conclude this, *in the case that G is cyclic* (because then, for a generator x, |x| = |G|).

******

to see specifically what i mean: suppose p = 13, and suppose d = 3.

first let's look at all 3rd powers of non-zero elements:

13 = 1
23 = 8
33 = 27 = 1
43 = 64 = 12
53 = (25)(5) = (12)(5) = 60 = 8
63 = (36)(6) = (10)(6) = 8
73 = (49)(7) = (10)(7) = 5
83 = (64)(8) = (12)(8) = 5
93 = (81)(9) = (3)(9) = 1
103 = (100)(10) = (9)(10) = 12
113 = (121)(11) = (4)(11) = 5
123 = (144)(12) = (1)(12) = 12

so here H = {1,5,8,12}.

now certainly we can take a = 12, m = 4. and it *is* true that 4(3)(4) = 1. but 4 only has order 6 in Z13*:

42 = 3
43 = 12
46 = 122 = 1, so that 12 = 43 only has order 2 in H. and thus we can only conclude from 12 = 43 that 2 divides (p-1)/d = 4.

on the other hand, choosing 5 or 8 leads to the desired conclusion at once.

Thanks!!!

4. ## Re: Need someone to check a proof for weak points

Let me test my understanding of the above post by Deveno. For part2 of my proof at the top to be correct, I need theorem that says something like this:
"If for every $a \in G$, $a^x=1$ then |G| divides x."
which I haven't so I must work with the generators of H and G.

Certainly I could not find such theorem in my books on abstract algebra after 10 minute search. The above statement might even be wrong (I'm quite interested in feedback on that point).

5. ## Re: Need someone to check a proof for weak points

no.

if G is CYCLIC and for every a in G, ak = e, then |G| divides k.

the cyclic part is important.

ok, back up a bit:

suppose that for some group G, and some element a, we know that ak = e, then we know |a| divides k. but how does this relate to |G|?

well we know |a| divides |G| as well, but all this tells us is |a| divides gcd(|G|,k). for example (in the group V like i described above) it might be that k = 6, |G| = 4, |a| = 2. certainly the statements:

|a| divides 6, and
|a| divides 4

are both true, but we can't conclude from this that 4 divides 6 (it doesn't).

but if G is cyclic, and a is a generator for G, then |a| = |G|. so proving |a| divides k then PROVES |G| divides k.

******

let's follow the proof you gave "substituting" the particular p, a, d, m and |H| i gave in my example:

Proof that 4 divides (13 - 1)/3 = 4:

we have 4 in Z13* with 12 = 43.

thus 124 = (43)4 = 412 = 1. (all true so far).

thus 4 ( = |H|) divides 4 (= (p-1)/d). (all true but the "thus").

what is wrong here? it turns out that 122 = 1, as well, but certainly |H| doesn't divide 2. all we know for sure is that |12| divides |H|, and |12| divides 4,

so |12| (which could be 1,2 or 4 (we don't know that the "a" you pick *isn't* the identity)) divides gcd(|H|,4). all we've shown is that |H| and 4 have a common divisor, |12|.

on the other hand, if |H| EQUALS |a|, then a(p-1)/d = 1 proves |a| divides (p-1)/d, and thus proves |H| divides (p-1)/d.

*****************

the logical flaw you are making in both parts of part (2) is "assuming too much" from ak = e. all this tells us is |a| is a divisor of k. it doesn't tell us what |a| actually *is*. it might be 1 (which doesn't tell us anything about the order of the group a lives in). to use an equation like:

ak = e *effectively*, you actually want "a lower bound" on |a|. ideally, |a| = G (G is cyclic).

and that's what you have here...you just don't *use* it.

6. ## Re: Need someone to check a proof for weak points

Yes, now I get it. My thanks to you sir !