prove HK = the set of units modulo n

Let p and q be distinct prime numbers and let n = pq. Show that $\displaystyle HK = \mathbb{Z}^x_n $ for the subgroups $\displaystyle H = \{[x] \in \mathbb{Z}^x_n | x \equiv 1 (mod \ p)\} $ and $\displaystyle 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 $\displaystyle xy \equiv y (mod \ p) $ and $\displaystyle xy \equiv x (mod \ q) $ which doesn't seem to help me much. then i tried saying that if $\displaystyle y \equiv 1 (mod p) $ and $\displaystyle 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 $\displaystyle 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.

Re: prove HK = the set of units modulo n

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

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

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

one is tempted, at first, to say that:

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

$\displaystyle x \equiv 1\ (mod\ p)$

$\displaystyle 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 $\displaystyle (\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:

$\displaystyle x \equiv 1\ (mod\ p)$

$\displaystyle 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) = $\displaystyle |(\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 $\displaystyle (\mathbb{Z}_n)^{\times}$ with the same order, it must be the entire group.

Re: prove HK = the set of units modulo n

where did you get $\displaystyle 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.

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.

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

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

$\displaystyle x \equiv 1\ (mod\ 3)$ , that is: $\displaystyle \{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:

$\displaystyle x \equiv 1\ (mod\ 3)$

$\displaystyle x \equiv 0\ (mod\ 5)$.

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

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

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 $\displaystyle HK \in \mathbb{Z}_n^{\times} $ but is it possible to show that $\displaystyle \mathbb{Z}_n^{\times} \in HK $?

Re: prove HK = the set of units modulo n

well, with that approach you want to prove that every $\displaystyle z \in (\mathbb{Z}_n)^{\times}$ is of the form $\displaystyle 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".

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 $\displaystyle \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 $\displaystyle \phi(p) $?

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.