2
$\begingroup$

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.

4 Answers 4

3

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.

  • 0
    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!2012-03-29
  • 0
    Also, would the same argument work for a smaller set of numbers that are relatively prime to 20, say, {1,3,7,9}?2012-03-29
  • 0
    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.2012-03-29
3

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.

2

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

  • 0
    Thank you and @hwhm for your prompt responses!2012-03-29
1

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 $$

  • 0
    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!2012-03-29
  • 0
    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).2012-03-29
  • 0
    Super; this makes my life so much easier. Thank you!2012-03-29
  • 0
    @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.2012-03-29
  • 0
    I understand now, thank you.2012-03-30