What are all the invertible elements in $\mathbb{Z_m}$ for $m = 30$?

Question

How can I know all of the invertible elements? Is it just all of the numbers that are relatively prime to 30?

These posts are also related: http://math.stackexchange.com/questions/117260/how-to-determine-all-the-invertible-elements and http://math.stackexchange.com/questions/82313/an-invertible-element-i-in-mathbb-z-n-must-be-coprime-to-n (And you can probably find more similar questions.) — Martin Sleziak, Jan 22 '14 at 09:15

score 2 · Accepted Answer · answered Jan 22 '14 at 02:43

2

Yes, you're correct. To prove this, note that the smallest number that can be written as a linear combination of $k$ and $30$ is the greatest common divisor of $k$ and $30$; if $k \in \mathbb{Z}_m$ is invertible, one can write

$$k s \equiv 1 \pmod{30} \iff ks + 30 r = 1$$

for appropriate $s, r$.

answered Jan 22 '14 at 02:43

So it doesn't matter whether $m$ is prime or not? – user3064097 Jan 22 '14 at 02:48
1

@user3064097 In general, no. But if $m$ is prime, it's really easy to see what it's relatively prime to. – Jan 22 '14 at 02:53
So if you have a composite composed of unique primes abc, what is the size of invertible elements, (a-1)(b-1)(c-1)? – user3064097 Jan 22 '14 at 03:03
@user3064097 Have a look at the totient function. – Jan 22 '14 at 03:06

score 0 · Answer 2 · answered Jan 22 '14 at 02:54

0

Yes, since $\, \exists\, x\!:\, ax\equiv 1\pmod{30}\iff \exists\, x,y\!: ax+30y = 1\iff \gcd(a,30)=1\,$ by Bezout.

answered Jan 22 '14 at 02:54

Bill Dubuque

272,048

What are all the invertible elements in $\mathbb{Z_m}$ for $m = 30$?

2 Answers2

Linked