# Checking if a set is closed under modular multiplication

I have to check if the set {1, 3, 7, 9, 11, 13, 17, 19} forms a group under multiplication modulo 20, and the only idea that I've had so far is: attempt brute force on all the elements (multiplying them all out and making a massive table), followed by induction on each element, to show that powers of each of them also belong to the set.

We've only started talking about groups and mod arithmetic last week, so I'm still trying to find my way around. I'm sure there's a better way to do this, and any advice would be much appreciated.

-

These are all the numbers between $0$ and $19$ which are relatively prime to $20$. It is almost obvious that the product of two numbers relatively prime to $m$ is itself relatively prime to $m$.

For a formal proof, let's concentrate on $m=20$. Suppose that $a$ and $b$ are relatively prime to $20$. We show that $ab$ must be relatively prime to $20$. For if it is not, then $ab$ is divisible by $2$ or by $5$ (or both). But if $ab$ is divisible by the prime $2$, then $a$ or $b$ must be. the argument for the prime $5$ is the same.

-
 That makes a ton of sense. It seems like a proof of this shouldn't be too hard, but I've had to eat those very words too many times before, haha. Thank you! – Chris Mar 29 '12 at 5:07 Also, would the same argument work for a smaller set of numbers that are relatively prime to 20, say, {1,3,7,9}? – Chris Mar 29 '12 at 5:11 It need not. The stressed fact that these are all the numbers (mod $20$) is what forces being closed under multiplication mod $20$. It so happens that the four numbers you mention are closed under multiplication mod $20$, but that is a more complicated fact. – André Nicolas Mar 29 '12 at 5:22 Thank you for the proof! – Chris Mar 29 '12 at 5:52

HINT. Note that each of the numbers you have is relatively prime to $20$, and that the set contains all numbers between $1$ and $20$ that are relatively prime to $20$.

-
 Thank you and @hwhm for your prompt responses! – Chris Mar 29 '12 at 5:07

The largest possible group of positive integers under multiplication modulo $n$ is that containing all of its units, i.e. all positive integers smaller than $n$ and relatively prime to it. In this case your set is exactly the one for 20.

-

In fact it is easy to check $\pm\{1, 3, 7, 9 \}$ is closed under multiplication and inversion, viz.

$$3\:\{3,7,9\}\equiv \{9,1,7\},\ \ \ 7\:\{7,9\}\equiv \{9,3\},\ \ \ 9\cdot 9\equiv 1$$

-
 Does this imply that the entire set is closed though? Wouldn't we have to prove (by induction maybe?) that, say, 3*(7^8) also belongs to the set? Or does this just follows from the property you've mentioned? Thanks! – Chris Mar 29 '12 at 5:46 A subset S is closed under multiplication iff $\rm\:s\cdot t\in S\:$ for all $\rm\:s,t\in S$. The above includes all such products, except the trivial $\rm\:1\cdot n\equiv n$. It's equivalent to checking only the upper triangular part of the multiplication table for S (exploiting commutativity). – Gone Mar 29 '12 at 6:12 Super; this makes my life so much easier. Thank you! – Chris Mar 29 '12 at 6:24 @Chris Note that I've also exploited the balanced residue system $0, \pm1, \pm2,\ldots\:$ This halves work since we can ignore signs. Combined with the commutativity optimization, this reduces the number of products needing checking by roughly a factor of $4$. But, generally, the method using unit groups is better. My point was simply to point out that the brute force approach is not as difficult as it may appear at first glance, if one does it smartly. – Gone Mar 29 '12 at 13:54 I understand now, thank you. – Chris Mar 30 '12 at 20:10