Need someone to check a proof for weak points

**mrproper** · August 12th 2012, 01:23 PM

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

**Deveno** · August 12th 2012, 02:24 PM

a few remarks:

the fact that ab = (m^d)(n^d) = (mn)^d relies on the fact that multiplication modulo p is commutative.

claim 2) and claim 3) of part 1) are superfluous, Z_p* 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 Z_p*, so that |m| = p-1. then it follows from a result on cyclic groups that:

a = m^d 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:

"....m^d|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, g^k = e, doesn't tell you k = |G| (for example, in V, the klein 4-group, it's true that g² = 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:

1³ = 1
2³ = 8
3³ = 27 = 1
4³ = 64 = 12
5³ = (25)(5) = (12)(5) = 60 = 8
6³ = (36)(6) = (10)(6) = 8
7³ = (49)(7) = (10)(7) = 5
8³ = (64)(8) = (12)(8) = 5
9³ = (81)(9) = (3)(9) = 1
10³ = (100)(10) = (9)(10) = 12
11³ = (121)(11) = (4)(11) = 5
12³ = (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⁽³⁾⁽⁴⁾ = 1. but 4 only has order 6 in Z₁₃*:

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

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

**mrproper** · August 12th 2012, 10:14 PM

Thanks!!!

**mrproper** · August 12th 2012, 11:12 PM

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

**Deveno** · August 13th 2012, 05:36 AM

no.

if G is CYCLIC and for every a in G, a^k = 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 a^k = 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 Z₁₃* with 12 = 4³.

thus 12⁴ = (4³)4 = 4¹² = 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 12² = 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 a^k = 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:

a^k = 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.

**mrproper** · August 13th 2012, 10:18 PM

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

Thread: Need someone to check a proof for weak points

LinkBack

Thread Tools

Display

Need someone to check a proof for weak points

Re: Need someone to check a proof for weak points

Re: Need someone to check a proof for weak points

Re: Need someone to check a proof for weak points

Re: Need someone to check a proof for weak points

Re: Need someone to check a proof for weak points

Similar Math Help Forum Discussions

question on one of the steps in a weak solution proof

Time Series - Stationarity (Weak) Proof - Help Needed

can someone check my coordinate points?

Please check my critical points

Determining whether 4 points are coplanar. Answer check

Search Tags