prove HK = the set of units modulo n

Let p and q be distinct prime numbers and let n = pq. Show that for the subgroups and .

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 and which doesn't seem to help me much. then i tried saying that if and then by CRT there exists a unique z such that z satisfies those congruences. if z = xy then by CRT 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 , and is abelian, so HK is a subgroup of .

now

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

one is tempted, at first, to say that:

, but this is incorrect. why? consider the two congruences:

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 .

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:

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

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

is this equal to φ(pq) = ?

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 with the same order, it must be the entire group.

Re: prove HK = the set of units modulo n

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

now, let's consider the elements of , [x], where:

, that is: .

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:

.

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

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 but is it possible to show that ?

Re: prove HK = the set of units modulo n

well, with that approach you want to prove that every is of the form .

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

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.