Find the invertible elements and zero divisors in the ring $(\mathbb{Z}_{21}, +, \cdot)$. For each invertible element find the inverse.

Question

this is the exercise I have:

In the ring $(\mathbb{Z}_{21}, +, \cdot)$:
i) Find the invertible elements;
ii) Find the zero divisors;
iii) For each invertible element find the inverse.

I have done this:
i)
since the $gcd(a,n) = 1$ where $a \ne 0\in \mathbb{Z}_{21}$ and $n = 21$, then the element $a$ has an inverse.
Or also, since $21 = 7 \cdot 3$, if $7 \nmid a \mbox{ and } 3 \nmid a$, then $a$ has an inverse.
Considering the things above, I have found them by inspection: $1,2,4,5,8,10,11,13,16,17,19,20$.
I know that they are few elements, and by attempts it is a good way, but, is there exists any algorithm to calculate them in a more rapid way?

ii)
since the $gcd(a,n) \ne 1$, or also since $21 = 7 \cdot 3$, if $7 \mid a \mbox{ and } 3 \mid a$, then $a$ is a zero divisor. So, by attempts, the zero divisors are $3,6,7,9,12,14,15,18$
Also, here, is there any other rapid algorithm to determine them?

iii)
for each invertible element must hold the following: $$ax \equiv 1 \mbox{ (mod 21) }$$ so,
$1x \equiv 1 \mbox{ (mod 21) }$
hence $1$ is the inverse of $1$.
$2x \equiv 1 \mbox{ (mod 21) }$
it means to solve this equation in $\mathbb{Z}_{21}$:
$\begin{array}{rcl}[2] \odot [x] & = & [1] \\ [2 \cdot x] & = & [1] \\ [2 \cdot 11 ] & = & [1] \\ [22] & = & [1] \\ [1] & = & [1]\end{array}$
so here the inverse of $2$ is $x = 11$.

In my book there is a hint: check if these following numbers are congruent modulo 21, they will help you to find the inverses:
$22,43,64,85,106,127,148,169,190,211,399=21 \cdot 19$
but, I don't know how to use them. Can you tell me anything about them?

Please, can you give any suggestions? Thanks!

Answer 1

we need :

$\begin{array}{rcl} 2x & \equiv & 1 & (\mod 21) & \Rightarrow \\ (2\times11 )x & \equiv & 1\times11 &( \mod 21)& \Rightarrow \\ x & \equiv & 11 &( \mod 21)& \end{array}$

$\begin{array}{rcl} 4x & \equiv & 1 & (\mod 21) & \Rightarrow \\ (4\times5 )x & \equiv & 1\times5 & (\mod21)& \Rightarrow \\ -x &\equiv& 5 &(\mod 21)& \Rightarrow \\ x &\equiv& -5& (\mod 21)& \\ & \equiv & 16& (\mod 21)& \end{array}$

$\begin{array}{rcl} 5x & \equiv & 1 & (\mod 21) & \Rightarrow \\ (4\times5 )x &\equiv & 1\times4 &(\mod21)& \Rightarrow \\ -x &\equiv& 4 &(\mod 21)& \Rightarrow \\ x &\equiv& -4 &(\mod 21)& \\ &\equiv& 17 &(\mod 21)& \end{array}$

$\begin{array}{rcl} 8x &\equiv& 1 &(\mod 21)& \Rightarrow \\ (2\times8 )x &\equiv& 1\times2 &(\mod21)& \Rightarrow \\ -5x &\equiv& 2 &(\mod 21)& \Rightarrow \\ -20x &\equiv& 8 &(\mod 21)& \Rightarrow \\ x &\equiv& 8 &(\mod 21)& \end{array}$

$\vdots$

and other elements in same way

Answer 2

Note: This is an unorthodox answer using claims that have not been verified by the mathematical community, but I couldn't resist taking the theory 'out for drive' and demonstrate how it doesn't 'fall off a cliff'.

Observe that when using this method we don't need Euler's totient function to get the count for the number of invertibles or identify them by checking for the numbers coprime to $21$. Rather, all the invertibles are 'lurking' in the factorization of larger numbers and are 'discovered' there by a 'combinatorial balancing' algorithm.

---

$\tag 1 1 \times 1 \equiv 1 \pmod{21}$

$\tag 2 20 \times 20 \equiv 1 \pmod{21}$

We will use our $\psi$-theory to find the remaining invertible elements.

$\quad 20,\quad \psi(20) = 110 \gt 21, \; \lambda(21,20) = 22 \;\,= 2 \times 11$
$\quad 19,\quad \psi(19) = 100 \gt 21, \; \lambda(21,19) = 43$
$\quad 18,\quad \psi(18) = 90 \;\,\gt 21, \; \lambda(21,18) = 64 \;\,= 2^6$
$\quad 17,\quad \psi(17) = 81 \;\,\gt 21, \; \lambda(21,17) = 85 \;\,= 5 \times 17$
$\quad 16,\quad \psi(16) = 72 \;\,\gt 21, \; \lambda(21,16) = 106 = 2 \times 53$
$\quad 15,\quad \psi(15) = 64 \;\,\gt 21, \; \lambda(21,15) = 127$
$\quad 14,\quad \psi(14) = 56 \;\,\gt 21, \; \lambda(21,14) = 148 = 2^2 \times 37$
$\quad 13,\quad \psi(13) = 49 \;\,\gt 21, \; \lambda(21,13) = 169 = {13}^2$
$\quad 12,\quad \psi(12) = 42 \;\,\gt 21, \; \lambda(21,12) = 190 = 2 \times 5 \times 19$
$\quad 11,\quad \psi(11) = 36 \;\,\gt 21, \; \lambda(21,11) = 211$
$\quad 10,\quad \psi(11) = 30 \;\,\gt 21, \; \lambda(21,10) = 232 = 2^3 \times 29$
$\quad 9,\quad \quad \psi(9) = 25 \;\,\gt 21, \; \lambda(21,9) \;= 253 = 11 \times 23$
$\quad 8,\quad \quad \psi(9) = 20 \;\,\le 21, \; \text{STOP}$

Presented with, say, $64 = 2^6$, a combinatorial 'balancing' argument must be used to get the inversion relationships, resulting in the 'uncovering' of

$\quad \overline 4 \times \overline 16 = \overline 1 \; \land \; \overline 8 \times \overline 8 = \overline 1$

and rejecting $2 \times 32 = 64$ since $32 \ge 21$.

Here are the invertbile integers $\text{modulo-}21$, that naturally come in pairs or singletons,

$\; 1$
$\; 2,11$
$\; 4,16$
$\; 8$
$\; 5,17$
$\; 13$
$\; 10,19$
$\; 20$