How to find all elements in Z/80 that have multiplicative inverses.

Question

I need to find all the elements in Z/80 that have multiplicative inverses. Z/80 is not a field, so I know not every element will have an inverse. Is there a shorter way than just writing out the entire multiplication table?

Answer 1

Use a sieve. Make a list from 1 through 80, and cross out every other number. Start again and cross out every 5th number. What remains is your invertible elements.

Answer 2

Hint: By Bezout's Lemma, we can find integers $m$ and $n$ such that

$$a m + 80 n = 1$$

if and only if $a$ is relatively prime to $80$.

Answer 3

By the euclidean algorithm, these are exactly those elements, for which $\rm{gcd}(n, 80) = 1$, as in that case we get $a,b \in \mathbb{Z}$ with $a \cdot n + b\cdot 80 = \rm{gcd}(n, 80) = 1$.

If $\rm{gcd}(n, 80) \neq 1$ it is easy to see that $n$ is not invertible modulo $80$.

Answer 4

Recall: It has already been said , but $ax \equiv 1 \mod c$ has a solution $\iff$ gcd$(a,c)=1$. Look at my comment under $T.Bongers$, one quick way to do this if you know how to code is to make a for loop which says, for(int $i = 0$; $i<80$; $i++$) and in the for loop make an if statement which says if i%(any divisor of $80$) do not print, else print. The divisors are $2,4,5,8,10,16,20,40.$. Hope this helps.