# How to determine all the invertible elements?

I have this excercise, I need your help on the third point:

i) Determine two integers $\alpha$ and $\beta$ such that $12\alpha + 7\beta = 1$

Answer: $\alpha = 3$ and $\beta = -5$

ii) Determine all the solutions of $$7x\equiv 1 (mod. 12)$$

Answer: $[-5]_{12} = \{-5+12k, k\in\mathbb{Z}\}$

iii) determine invertible elements (for product) for $(\mathbb{Z}_{12}, +, \cdot)$, and zero divisors

Answer: Here I need your help! How can I determine all invertible elements and all zero divisors?

iv) determine, if exists, a class $[a]\in\mathbb{Z}_{12}$ such that $[a]=.$

Answer: No, doesn't exist. $gcd(6,12)\neq 1$

There is the brute force method: try them all!

2 (2x6=12=0), 3 (3x4=12=0), 4 (4x3=12=0), 6 (6x2=12=0), 8 (8x6=48=0), 9 (9x4=36=0), 10 (10x6=60=0) are zero divisors

1, 5 (5 x 5 = 25 = 1), 7 (7 x 7 = 49 = 1), 11 (11x11=121=1) are units.

Notice that the units have gcd 1 with 12...

• I've alredy thinked of that. Is there something much elegant? – BAD_SEED Mar 6 '12 at 23:00
• This is quite elegant as it is. The units are relatively prime to 12, and the zero-divisors are not. – Brett Frankel Mar 6 '12 at 23:03
• and what if the same question is for $\mathbb{Z}_{200}$ or something bigger? – BAD_SEED Mar 6 '12 at 23:37
• If the ring is $\mathbb{Z}_{200}$ and the question is "list all invertible elements and zero divisors", then there are going to be 199 answers no matter what you do. But it should be easy enough to list all the zero divisors of $\mathbb{Z}_{200}$: its prime factors are 2 and 5, so list all the multiples of 2 and 5. – Tanner Swett Mar 7 '12 at 0:18

On iv), your answer is right, but the justification is not. For example, it is easy to see that there are $[a]$ such that $[a]=$, even though $\gcd(6,12)\ne 1$. For $a=1$ will work, so will $a=3$, as will $a=9$.

The reason that we do not have an $a$ such that $[a]=$ is that $\gcd(6,12)$ does not divide $2$. For if $[a]=$, then $6a\equiv 2 \pmod {12}$, or equivalently $12$ divides $6a-2$. If this happens, then $6$ divides $6a-2$, which implies that $6$ divides $2$. That is clearly not the case.

Or else we could say that there is no $a$ such that $[a]=$ because we tried everything from $a=0$ to $a=11$, and nothing worked. What's fine for a small modulus like $12$, but one would not care to do that with $1200$.

Hint $\rm\ n\:$ invertible in $\rm\mathbb Z_{12}\iff \exists\: a\!:\: an\equiv 1\iff \exists\: a,b\!:\: an+12b = 1\iff gcd(n,12)=1$

Conversely, $\rm\: gcd(n,12) = c > 1\:\Rightarrow\: n(12/c) \equiv 12(n/c) \equiv0\:\Rightarrow\: n\:$ is a zero-divisor, if $\rm n\not\equiv 0$.

An element $$a$$ is invertible in this finite structure if and only if there exists an $$n \ge 1$$ such that

$$a^n = 1$$

Here is what I entered in the first row for columns A-F:

1 =mod(A1*$$A1,12) =mod(B1*$$A1,12) =mod(C1*\$A1,12) =countif(A1:D1,1) =if(E1>0,"Invertible","")


So you drag it down putting numbers in the A column.

Result: So the invertible elements are in the multiplicative subgroup $$\{1,5,7,11\}$$.