How many elements are there in $\mathbb{Z}^{\times}_{20}$ ,the subset of multiplicatively invertible elements in $\mathbb{Z}_{20}$?

Question

How many elements are there in $\mathbb{Z}^{\times}_{20}$ ,the subset of multiplicatively invertible elements in $\mathbb{Z}_{20}$ ?

I tried to prepare a Cayley Table for the above. But there are 19 elements in rows and columns this looks very complicated. Also I know that group order is 19.

Can someone please give me a hint to work this?

Answer 1

Why do a two dimensional table when you can test the 20 values individually?

$0*a \equiv 1$ is clearly impossible so $0$ is not invertible.

$1*1 \equiv 1$ so $1$ is.

$2*x \equiv 1 \pmod {20}$. Hmmm, is that invertable?

$2x = 1 + 20k$ so $x = \frac 12 + 10k$ and that is not an integer. So $2$ is not convertible.

$3x \equiv 1$. Hmm, $3x = 1 + 20k$... well if $k =1$ then $3x = 21$ and $x = 7$ so $3$ (and $7$) are.

$4x \equiv 1$ is that possible?

Well $4x = 1 + 20k$ so $x = \frac 14 + 5x$. That's just like $2$. If $a|20$ then $ax= 1 + 20k\implies x = \frac 1a + (\frac {20}a)k$ is not an integer so if $a|20$ then $a$ is not invertible. That rules out $2,4,5,10$.

What about $6$. $6x = 1+ 20k \implies 3x = \frac 12 + 10k$ and that can't be an integer. Not only if $a|20$ is $a$ not invertible; If $a$ has any factors in common it is not invertible.

That rules out $2,4,5,6,8,10,12,14,15,16,18$ and only leaves the numbers that are relatively prime.

So if $\gcd(a,20) = 1$ and we want to solve $ax = 1 + 20k$, when can we do that. Well, that means $ax -20k = 1$ and by Bizout's Lemma we can alwasy solbe that if $a$ and $20$ are are relatively prime.

So we have stumbled across the Theorem.

Theorem: $a$ is invertible in $\mathbb Z_{n}^\times$ if and only if $a$ and $n$ are relatively prime.

There numbers that are relatively prime to $20$ are those that are not divisible by $2$. I.e. $1,3,5,..., 19$. There are $10$ of those. And of those, those that are not divisible by $5$. There are $2$ that are divisible by $5$ so there are $8$ that are not.

There are $8$ relatively prime numbers: $1,3,7,9,11,13,17,18$ and they are the only ones that are invertible.

For the record:

$1^{-1} \equiv 1;$

$3^{-1} \equiv 7;$

$7^{-1} \equiv 3;$

$9^{-1} \equiv 9;$

$11^{-1} \equiv 11;$

$13^{-1} \equiv 17;$

$17^{-1} \equiv 13;$

$19^{-1} \equiv 19;$

Answer 2

An element $a\in\mathbb{Z}_{20}$ is invertible iff $gcd(a,20)=1$. So the invertible elements are the integers from $1$ to $19$ that don't share any common divisors with $20$.