prove HK = the set of units modulo n

Printable View

October 17th 2011, 04:40 PM
oblixps

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.
October 17th 2011, 06:17 PM
Deveno

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.
October 17th 2011, 09:57 PM
oblixps

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.
October 17th 2011, 10:19 PM
Deveno

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.
October 18th 2011, 01:01 AM
oblixps

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$ ?
October 18th 2011, 01:43 AM
Deveno

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".
October 18th 2011, 08:34 AM
oblixps

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)$ ?
October 18th 2011, 01:59 PM
Deveno

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.