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
    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
    I understand now, thank you.2012-03-30