Finding invertible elements in $\mathbb{Z}/m\mathbb{Z}$

Question

Can anyone show me how to find invertible elements in $\mathbb{Z}/m\mathbb{Z}$, $m$ is say $28$?

Also I'm not very clear about what it mean by 'invertible element in $\mathbb{Z}/m\mathbb{Z}$'

Some related posts: http://math.stackexchange.com/questions/647036/what-are-all-the-invertible-elements-in-mathbbz-m-for-m-30 http://math.stackexchange.com/questions/117260/how-to-determine-all-the-invertible-elements http://math.stackexchange.com/questions/82313/an-invertible-element-i-in-mathbb-z-n-must-be-coprime-to-n — Martin Sleziak, Jan 22 '14 at 09:15

score 8 · Accepted Answer · answered Jan 22 '14 at 07:09

8

An invertible element is one which has a "buddy" whom when operated together, produces the identity. In short, if $a\in\mathbb{Z}/m\mathbb{Z}$ is an invertible element, then there exist a $b\in\mathbb{Z}/m\mathbb{Z}$ such that $$ab\equiv1\mod m$$

Expressing the congruence in the usual way, we have $$ab+km=1$$ for some $k\in\mathbb{Z}$.

So, can you see how we can try to use relative primes, the Euclidean algorithm etc. ?

answered Jan 22 '14 at 07:09

BlackAdder

4,029

1

so any number that's coprime with m is invertible? – Arch1tect Jan 22 '14 at 07:12
Yup! Well done! – BlackAdder Jan 22 '14 at 07:13
Well and creatively worded indeed! +1! – mathematics2x2life Jan 22 '14 at 07:30

score 1 · Answer 2 · edited Jan 22 '14 at 10:13

1

An element, $x\in\mathbb{Z}_m$ is invertible if there is another element $y\in\mathbb{Z}_m$ such that $xy \equiv 1 (mod\ m)$.

An element is invertible iff it is relatively prime with $m$. For example, with $m = 28$, $4$ is not invertible because $\gcd(28,4) = 4$, but $17$ is, because $\gcd(28,17) = 1$.

edited Jan 22 '14 at 10:13

Martin Sleziak

53,687

answered Jan 22 '14 at 07:09

Davis Yoshida

1,530

Finding invertible elements in $\mathbb{Z}/m\mathbb{Z}$

2 Answers2

Linked

Related