3
$\begingroup$

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!

$\endgroup$
4
  • 1
    $\begingroup$ Note that $1\equiv 1+21\equiv 22$ and similarly $1\equiv 1+2\cdot 21 \equiv 43$ etc... so the list of numbers they give you are all elements of the equivalence class of $1$. The hint is giving you a (partial) list of possible elements you can look for as outcomes of multiplications for elements to find the inverses with. E.g. $4\cdot 37=148$ and $148$ is on the list so therefore... $\endgroup$ – JMoravitz Feb 17 '17 at 1:15
  • $\begingroup$ @JMoravitz Can you add some other details as answer below? I would want to accept your answer as the best one. $\endgroup$ – JB-Franco Feb 19 '17 at 19:08
  • $\begingroup$ Note that if $ax\equiv1\pmod{21}$ then $x$ is the inverse of $a$, but also $a$ is the inverse of $x$. In particular $a$ and $x$ are both units. You have already listed all $12$ units, so now you need only to pair them up correctly. This is a matter of performing a few multiplications; as always $1^{-1}=1$ and $20^{-1}=(-1)^{-1}=-1=20$. This leaves $10$ elements to pair off. $\endgroup$ – Servaes Feb 20 '20 at 14:09
  • 1
    $\begingroup$ Moreover, as you have $20\times20\equiv1$ and $20=2\times10=4\times5$, you immediately get \begin{eqnarray*} 2^{-1}&=&10\times20&=&11\\ 4^{-1}&=&5\times20&=&16\\ 5^{-1}&=&4\times20&=&17\\ 10^{-1}&=&2\times20&=&19, \end{eqnarray*} leaving just the units $8$ and $13$. A quick check shows that $8\times13\neq1$ so $8^2=13^2=1$. $\endgroup$ – Servaes Feb 20 '20 at 14:14
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ it is not clear ... why after $-20x \equiv 8 \mbox{ (mod 21) }$ follows $\equiv 17$? $\endgroup$ – JB-Franco Feb 19 '17 at 23:00
  • $\begingroup$ Soory, I copy last step , then edit and I forgot remove $\equiv 17$ . I edit my answer, $-20\equiv 1 (mod 21)$, not follows $\equiv 17$, $\endgroup$ – Mustafa Feb 20 '17 at 0:50
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.