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!
Best Answer
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