Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - Need someone to check a proof for weak points

  1. #1
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    101
    Thanks
    4

    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.
    Last edited by mrproper; August 12th 2012 at 02:28 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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 from mrproper
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    101
    Thanks
    4

    Re: Need someone to check a proof for weak points

    Thanks!!!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    101
    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    101
    Thanks
    4

    Re: Need someone to check a proof for weak points

    Yes, now I get it. My thanks to you sir !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. question on one of the steps in a weak solution proof
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: November 20th 2011, 08:36 PM
  2. Time Series - Stationarity (Weak) Proof - Help Needed
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: September 13th 2010, 09:12 PM
  3. can someone check my coordinate points?
    Posted in the Geometry Forum
    Replies: 1
    Last Post: June 3rd 2010, 11:25 PM
  4. Please check my critical points
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 19th 2008, 05:11 AM
  5. Replies: 2
    Last Post: October 26th 2008, 07:18 AM

Search Tags


/mathhelpforum @mathhelpforum