Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
A related problem. –  Mhenni Benghorbal Mar 11 '13 at 20:25
add comment

4 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
show 7 more comments

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

share|improve this answer
    
Yes, I am aware of that, but still. –  haunted85 Mar 10 '13 at 13:20
1  
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
add comment

CRT $ $ (Chinesese Remainder Theorem) $ $ gives an inverse reciprocity formula that enables one to calculate $\rm\,\ x^{-1} mod\ y\,\ $ from $\rm\,\ y^{-1} mod\ x.\: $ This proves handy when $\rm\:x\:$ is small, e.g. in your case

$\begin{eqnarray} \rm CRT\ &\Rightarrow&\rm\ \ x\,(x^{-1}mod\ y) &+&\, \rm y\,(y^{-1} mod\ x)\ \ \equiv\ \ 1\ \ \ \,(mod\ xy)\quad\ when\quad (x,y)=1 \\ \\ &\Rightarrow& \rm\ \ \ \ \ x^{-1}mod\,\ y &\,\equiv\: &\rm \dfrac{1\ +\ y\ \ (-y^{-1} mod\ x)}x\ \ \ (mod\ y)\quad\ {\bf [Inverse\ Reciprocity]} \\ \\ &\Rightarrow& \rm\ \ 13^{-1}\, mod\ 210\,\ &\equiv&\rm \dfrac{1\ +\ 210\ \ (-210^{-1}\,mod\ 13)}{13} \\ \\ && &\equiv&\rm \dfrac{1 + (\color{#C00}2 + 13\cdot 16)\,(-{\color{#C00}2}^{-1}\!\!\equiv \color{#0A0}{6}\,\ mod\ 13)}{13}\\ && &\equiv\,&\rm \dfrac{1 + (\color{#C00}{2})\,\color{#0A0}{6}}{13}\, +\, (16)\,\color{#0A0}{6} \,\equiv\, 97\ \ \ (mod\ 210) \end{eqnarray}$

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

share|improve this answer
    
Nice, +1 ${}{}$ –  Pedro Tamaroff Mar 11 '13 at 1:48
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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