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

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?

• If you start calculating the powers of the elements you should soon see a pattern that will tell you when you ever reach $1$. You could try this for $\mathbb{n}$ for smaller values of $n$ (perhaps $5, 6, 12$ ) first. Hint: greatest common divisor. – Ethan Bolker Dec 18 '18 at 17:32
• A number has a mod mul inv iff it is coprime to mod. Look up modular mul inv – qwr Dec 18 '18 at 17:33
• @Kaynex False. 14 doesn't divide 20, yet is non-invertible. – Don Thousand Dec 18 '18 at 17:40
• Look up the Euler Totient Function. Note that $$|\mathbb Z_{n}^\times|=\phi(n)$$ – Don Thousand Dec 18 '18 at 17:42

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

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