Results 1 to 8 of 8

Math Help - prove HK = the set of units modulo n

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    249

    prove HK = the set of units modulo n

    Let p and q be distinct prime numbers and let n = pq. Show that  HK = \mathbb{Z}^x_n for the subgroups  H = \{[x] \in \mathbb{Z}^x_n | x \equiv 1 (mod \ p)\} and  K = \{[y] \in \mathbb{Z}^x_n | y \equiv 1 (mod \ q)\} .

    Hint: use the chinese remainder theorem to show that the sets are the same.

    so i have that any element of HK is of the form xy (mod pq) and i also know that gcd(p, q) = 1 which hints to me that i can use the chinese remainder theorem somehow. i have that  xy \equiv y (mod \ p) and  xy \equiv x (mod \ q) which doesn't seem to help me much. then i tried saying that if  y \equiv 1 (mod p) and  x \equiv 1 (mod q) then by CRT there exists a unique z such that z satisfies those congruences. if z = xy then by CRT  xy \equiv 1 (mod pq) => xy \equiv 1 (mod n) so the element xy is in the set of units modulo n. I don't know if my reasoning was correct though. i "forced" y to be congruent to 1 (mod p) but since it was already congruent to 1 (mod q) it seems that y must be in other set and same for the x's so i essentially made H = K i think. i also have to prove the reverse inclusion which is that the set of units modulo n is contained in HK which i do not know how to proceed with. can someone help me with the "forward" and "backwards" directions of this proof? or if i don't need to consider the forward and backwards cases how would i proceed? thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prove HK = the set of units modulo n

    H,K are both subgroups of (\mathbb{Z}_n)^{\times}, and (\mathbb{Z}_n)^{\times} is abelian, so HK is a subgroup of (\mathbb{Z}_n)^{\times}.

    now |HK| = \frac{|H||K|}{|H \cap K|}

    first question: what is |H| and |K|?

    one is tempted, at first, to say that:

    H = \{1,1+p,1+2p,\dots,1+(q-1)p\}, but this is incorrect. why? consider the two congruences:

    x \equiv 1\ (mod\ p)
    x \equiv 0\ (mod\ q)

    by the CRT, this has a unique solution (mod pq). therefore, one (and only one) of the numbers (mod pq) 1,1+p,1+2p,....,1+(q-1)p is not in (\mathbb{Z}_n)^{\times} .

    therefore |H| = q-1 = φ(q), and similarly, |K| = p-1 = φ(p).

    second question: what is |H∩K|?

    if x is in H∩K, this means:

    x \equiv 1\ (mod\ p)
    x \equiv 1\ (mod\ q)

    which, again, by the CRT, has a unique solution (mod pq), namely, 1.

    thus, |HK| = φ(p)φ(q).

    is this equal to φ(pq) = |(\mathbb{Z}_n)^{\times}|?

    we can verify this by counting the positive integers less than pq, co-prime to pq.

    if gcd(x,pq) > 1, then x is either a multiple of q, or a multiple of p (can't be both, since pq isn't less than pq).

    multiples of p: p,2p,.....,(q-1)p, we have q-1 of these (and q doesn't divide any of these)

    multiples of q: q,2q,....,.(p-1)q, we have p-1 of these (and p doesn't divide any of these).

    so φ(pq) = (pq-1) - (p-1) - (q-1) = pq - 1 - p + 1 - q + 1 = pq - p - q + 1 = (p-1)(q-1).

    since HK is a subgroup of (\mathbb{Z}_n)^{\times} with the same order, it must be the entire group.
    Last edited by Deveno; October 18th 2011 at 02:56 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    249

    Re: prove HK = the set of units modulo n

    where did you get  x \equiv 0 (mod \ q) from? i understand the first congruence relation since we are considering an x in the set H but i'm not sure how you came up with the second one.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prove HK = the set of units modulo n

    in determining the order of H, we want to make sure that we only have invertible elements of the form 1+kp (mod pq).

    well, 1+kp is co-prime to p, no matter "what" k is. but it might not be co-prime to q.

    here is an example: let p = 3, q = 5.

    (\mathbb{Z}_{15})^{\times} = \{1,2,4,7,8,11,13,14\}

    now, let's consider the elements of \mathbb{Z}_{15}, [x], where:

    x \equiv 1\ (mod\ 3) , that is: \{1,4,7,10,13\}.

    not all of these are units, 10 is not co-prime to 5 (hence not co-prime to 15).

    this is the same as solving the two congruences:

    x \equiv 1\ (mod\ 3)
    x \equiv 0\ (mod\ 5).

    since (3,5) = 1, the chinese remainder theorem says we have the unique solution:

    x = 1(5)[5^{-1}]_3 + 0(3)[3^{-1}]_5\ (mod\ 15)

    now 5 = 2 (mod 3), so the inverse of 5 (mod 3) is the inverse of 2 (mod 3), which is 2 (mod 3) (checking (5)(2) = 10 = 1 (mod 3)).

    so the solution to this pair of congruences is 1(5)(2) = 10 (mod 15), and sure enough, 10 is the element that is not a unit.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    Posts
    249

    Re: prove HK = the set of units modulo n

    thanks for the detailed example and explanation! so i see that this is a "counting method" but i was wondering if my original intent was still possible. that is, it seems pretty clear that  HK \in \mathbb{Z}_n^{\times} but is it possible to show that  \mathbb{Z}_n^{\times} \in HK ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prove HK = the set of units modulo n

    well, with that approach you want to prove that every z \in (\mathbb{Z}_n)^{\times} is of the form z = xy, x \in H, y\in K.

    the trouble is, you only have z to work with, with no constructive way to find x and y.

    for example, mod 15, how do you "factor" 2 into mod 3 and mod 5 factors? it turns out that 2 = (7)(11), but that isn't "obvious".
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2008
    Posts
    249

    Re: prove HK = the set of units modulo n

    for the counting method, after thinking for a while i am a little unsure of why the chinese remainder theorem was needed. in your method it was used to find the unique number that was relatively prime to p but not q and then you concluded that H is the set of numbers mod p relatively prime to p so its cardinality is equal to  \phi(p) . but it seems like using the CRT was extraneous since we already know that once again H is the set of number relatively prime to p mod p so by definition isn't |H| already  \phi(p) ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prove HK = the set of units modulo n

    ah, i noticed a typo....|H| ISN"T φ(p), it's φ(q). H isn't the set of units mod p, it's the numbers congruent to 1 mod p in the units mod pq.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that 2 is a primitive root modulo p.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 21st 2010, 06:51 PM
  2. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 10:04 AM
  3. Replies: 1
    Last Post: October 6th 2009, 12:11 AM
  4. Replies: 3
    Last Post: November 15th 2008, 05:18 AM
  5. Algebra.....units prove
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 28th 2006, 06:29 PM

Search Tags


/mathhelpforum @mathhelpforum