0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ethan Bolker Dec 18 '18 at 17:32
  • $\begingroup$ A number has a mod mul inv iff it is coprime to mod. Look up modular mul inv $\endgroup$ – qwr Dec 18 '18 at 17:33
  • $\begingroup$ @Kaynex False. 14 doesn't divide 20, yet is non-invertible. $\endgroup$ – Don Thousand Dec 18 '18 at 17:40
  • 1
    $\begingroup$ Look up the Euler Totient Function. Note that $$|\mathbb Z_{n}^\times|=\phi(n)$$ $\endgroup$ – Don Thousand Dec 18 '18 at 17:42
1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.