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?

$$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}$$

• I was using the wrong number, thank you. I was goin' crazy. – haunted85 Mar 10 '13 at 13:32
• Any time, haunted...some times little things just escape us. – DonAntonio Mar 10 '13 at 13:33
• @DonAntonio: this process is essentially contained in the algorithm that I outline here (and use in my answer). – robjohn Mar 11 '13 at 23:53
• Perhaps @robjohn, though I don't see it that clear. What I did above is high school stuff and, imo, way simpler in this case, at least. – DonAntonio Mar 11 '13 at 23:56
• @DonAntonio: if it is not obvious, then I need to rewrite the description of the algorithm, as it is also high school stuff (just the Euclidean algorithm with bookkeeping inspired by Wallis that does the backward work at the same time as the forward work), – robjohn Mar 12 '13 at 0:03

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}$$

• Nice, +1 ${}{}$ – Pedro Tamaroff Mar 11 '13 at 1:48
• See also this question on an exercise from Knuth, Concrete Mathematics. – Bill Dubuque Jan 24 '15 at 20:19

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$).

• Yes, I am aware of that, but still. – haunted85 Mar 10 '13 at 13:20
• Your result $210 = 13\cdot 16 + 2$ doesn't have this form. So you got something wrong with the Euclidean algorithm. Double-check your computations on that (or post them here, if you can't find the mistake). – azimut Mar 10 '13 at 13:21

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}$.