Solving $13\alpha \equiv 1 \pmod{210}$ Determine $n \in \mathbb N$ among $12 \leq n \leq 16$ so that $\overline{n}$ is invertible in $\mathbb Z_{210}$ and calculate $\overline{n}^{-1}$.
In order for $n$ to be invertible in $\mathbb Z_{210}$, then $\gcd(210,n)=1$ so I need to look  into the following set
$$\left\{n\in \mathbb N \mid 12 \leq n\leq 16 \;\wedge\;\gcd(210,n)=1\right\} = \{13\}$$
calculating the inverse for $\overline{13} \in \mathbb Z_{210}$ means solving the following equation:
$$13\alpha \equiv 1 \pmod{210}$$
if I try to solve this with the Euclid's algorithm I get
$210 = 13 \cdot 16 +2\\16=2\cdot 8$
what am I missing here? Why that equivalence seems unsolvable?
 A: CRT $ $ (Chinesese Remainder Theorem) $ $ yields a handy  inverse reciprocity formula - which  enables us to calculate  $\rm\ \ x^{-1}\bmod  y\ \ $ from $\rm\ \ y^{-1}\bmod x,\,$ namely
$\begin{align} \rm CRT\ \Rightarrow\rm \ x\,(x^{-1}\bmod y)\ &\rm +\ y\,(y^{-1}\bmod x)\  \equiv\ 1\!\pmod{xy}\quad when\quad (x,y)=1 \\[.5em]
\Rightarrow \rm\ \ \ \ \ \  x^{-1}\bmod y\ \ &\equiv\: \rm \dfrac{1\ +\ y\, (\color{#c00}{-y^{-1}\bmod x})}x\!\pmod{\! y}\quad\ {\bf [Inverse\ Reciprocity]} \\[.5em]
\Rightarrow\! \rm\ \ 13^{-1}\bmod 210\ & \equiv\ \rm \dfrac{1\ +\ 210\ \ (-210^{-1}\,mod\ 13)}{13} \\[.5em] 
&\equiv\rm\ \dfrac{1 + (\color{#90f}2 + 13\cdot 16)\,(-{\color{#90f}2}^{-1}\!\!\equiv \color{#0A0}{6}\,\bmod 13)}{13\ \ }\\[.5em] 
&\equiv\rm\ \dfrac{1 + (\color{#90f}{2})\,\color{#0A0}{6}}{13}\, +\, (16)\,\color{#0A0}{6} \,\equiv\, 97\!\pmod{\!210} \end{align}$
To remember it, view it fractionally as forcing $\dfrac{1}x\pmod{\!y}\,$ to be an exact quotient by replacing the top $\,1\,$ by a congruent integer $\,1+yk\,$ where $\,x\mid 1+yk,\,$ i.e. $\color{#c00}{\bmod x}\!:\, yk\equiv -1,\,$ so $\,\color{#c00}{k\equiv -y^{-1}}.\,$ Rather than computing $\,y^{-1},\,$ often we can "twiddle" the top by testing if small values of $\,k\,$ work.
See here and here and here for many more worked examples of this (and many other) methods to compute modular inverses and fractions.
Remark $\ $ Once one knows the method, the calculation amounts to the prior two lines, which is a bit quicker than using the EEA = extended Euclidean Algorithm  (which is, essentially, equivalent). For example, compared to the back-substitution EEA in DonAntonio's answer we see that the above uses smaller numbers, because the form of the inversion formula allows us to cancel $13$ before performing any multiplications. Generally the arithmetic will be a bit simpler due to this.
For completeness, here is the inversion algorithm and a complete proof (without using CRT).
$\begin{eqnarray}    
{\bf Lemma}\ \ &&\rm y &=&\rm  \ \ \,r \,  +\,  q x &\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\rm e.g.\  &\ \ 210\ \,= \ \:2 +\! 16\cdot 13 &&\rm\ \ (1)\ \ find\ \ r \ =\,\ y\ \ \,mod \ x\\
             &&\rm 1 &=\,&\rm  r'r\, +\, p x & &\ \ 1 =\! (-6)2 \,+\, \color{#C00}1\cdot 13 &&\rm\ \ (2)\ \ find\ \ r' = r^{-1}\ mod\ x \\                                                    
\Rightarrow  &&\rm 1 &\equiv&\rm x\,(\color{#0A0}{p - q r'})\ \ \  (mod\ y)& &\ \ 1 \equiv 13(\color{#C00}1-16(-6)) &&\rm\ \ (3)\ \ find\,\ x' = x^{-1}\, mod\ y\\
{\bf Proof\quad\ }  &&   &=&\rm 1\!-\!rr'\!\!-\!xqr'\! & &\ \ \phantom{1} \equiv 13\cdot 97&&\rm\ \ \phantom{(3)\   find }x^{-1}\! =\, determinant\\ 
                      &&    &=&\rm 1\!-\!(r\!+\!qx)r'\! = 1\!-\!yr'\!\equiv 1\!\!\!\!\!\!\! && &&\rm\ \ \phantom{(3)\ \ find\,\ x' =} \ (see\ below)
\end{eqnarray}$
The  algorithm is very easy to remember since the $\rm\color{#0A0}{formula}$ for $\rm\:x^{-1}\:$ is just the determinant of the system of linear equations! Indeed, the Lemma has a more insightful proof by Cramer's Rule.
$\begin{eqnarray}
\begin{array}{l}{\bf Lemma}\\ \phantom{.}\end{array}\quad\ \begin{array}{l} \rm  y = \ \ \,  r + q\,x\\ \rm 1 = r'r + p\,x\end{array}\ \Rightarrow\  
\left[\begin{array}{c}\rm  y\\ \rm  1\end{array}\right]\! &=& \left[\begin{array}{cc}\rm 1 &\rm q\\ \rm r' &\rm p\end{array}\right] \left[\begin{array}{c}\rm  r\\ \rm x\end{array}\right]\ \Rightarrow\,\ \rm x^{-1}\! = det = p\!-\!qr'\ \ (mod\ y)  \\ \\
\begin{array}{l}\rm {\bf Proof}\quad\ \  By\ Cramer\\ \phantom{.}\end{array}\ \ \ \ \ \  \left[\begin{array}{cc}\rm 1 &\rm y\\ \rm r' &\rm 1\end{array}\right]\!&=&\left[\begin{array}{cc}\rm 1 &\rm q\\ \rm r' &\rm p\end{array}\right] \left[\begin{array}{cc}\rm 1 &\rm r\\ \rm 0 &\rm x\end{array}\right]\\ \\
\rm Taking\ \ det\  \Rightarrow\ 1-yr'  &=&\rm\ (p-qr')\ x \quad \Rightarrow\quad 1 \,\equiv\, (p-qr')\,x\ \ \ (mod\ y)\end{eqnarray}$
A: You correctly determined $13$ as the only invertible number in the given range.
Hint: The result of the extended Euclidean algorithm should have the form $13a + 210b = 1$.
EDIT: Looking at DonAntonio's answer, I think you only did the first step of the Euclidean algorithm. You need to repeat the division with remainder until eventually you get the remainder $0$ (or if you overlook the consequences, when you get $1$).
A: $$210=13\cdot 16+2\\13=6\cdot2 +1\\2=2\cdot 1$$
So going backwards:
$$1=13-6\cdot 2=13-6(210-13\cdot 16)=97\cdot 13+(-6)\cdot210\Longrightarrow$$
$$\Longrightarrow 13^{-1}=97\pmod{210}$$
A: Using the Euclid-Wallis Algorithm:
$$
\begin{array}{rrrrr}
&&16&6&2\\\hline
1&0&1&\color{#C00000}{-6}&13\\
0&1&-16&\color{#C00000}{97}&-210\\
210&13&2&\color{#C00000}{1}&0
\end{array}
$$
The red column says that $(\color{#C00000}{-6})210+(\color{#C00000}{97})13=\color{#C00000}{1}$.
