-1

I have found two different methods for finding the multiplicative inverse of a number modulo $n$ in $\mathbb{Z}/n\mathbb{Z}$.

One is using the Extended Euclidean Algorithm, which produces a different result to the much faster approach below.

Say I am trying to find the multiplicative inverse of the value $5$ in $\mathbb{Z}/8\mathbb{Z}$.

$$\begin{split} 5x &= 1+8n\\ x &= \frac{1 + 8n}{5}\\ \end{split}$$

Then find the smallest value of $n$ that makes $x$ an integer. In this case, $n=3$ which produces an inverse value of $5$.

Is this a correct method?

C-RAM
  • 2,377
  • 7
  • 12
  • 22
Benjamin McDowell
  • 1
  • You should get the same result if you do it right, since there's only one inverse. You can always check for correctness: $x \cdot x^{-1} \equiv 1 \mod n$. – Robert Israel Jan 24 '23 at 21:13
  • How is this less work-intensive that multiplying $5$ by $1$, $2$, $3$, etc until you get one that is one more than a multiple of $8$? You are multiplying $8$ by $1$, $2$, $3$, etc. until you hit one that is one less than a multiple of $5$. Granted, detecting multiples of $5$ is straightforward, but how much work would you have to do to find the inverse of $17$ modulo $215$? – Arturo Magidin Jan 24 '23 at 21:16
  • But 1 mod any number is always 1...@RobertIsrael – Benjamin McDowell Jan 24 '23 at 21:35
  • Yes, and we can finish via $\bmod 5\!:\ \color{#c00}n\equiv \dfrac{1}{-8}\equiv \dfrac{6}2\equiv \color{#c00}3,\,$ hence $\bmod 8\!:\ \dfrac{1}5\equiv \dfrac{1+8(\color{#c00}3)}5\equiv 5.\ $ This is the [inverse reciprocity method](https://math.stackexchange.com/a/3434593/242) in the linked dupe (essentially an optimization of the Extended Euclidean Algorithm when it terminates in two steps). See there and its links for many more methods. $\ \ $ – Bill Dubuque Jan 24 '23 at 21:48
  • @Arturo It ends up being less work since it reduces the inversion modulus (from $\color{#0a0}8$ to $\color{#c00}5),\,$ i.e. we reduce from computing $\,\color{#c00}5^{-1}\pmod{\!\color{#0a0} 8}\,$ to $\,\color{#0a0}8^{-1}\pmod{\!\color{#c00}{\!5}},\,$ hence the name $\rm inverse\ \color{#0a0}{recip}\color{#c00}{rocity}$. – Bill Dubuque Jan 24 '23 at 22:18
  • That's not a huge optimization in this instance - but it is when the modulus is much larger than $\color{#0a0} 8,\,$ e.g. to compute the inverse of $5$ mod $n = 1000000001$ we reduce to computing the inverse of $n\equiv 1\pmod{\!5}\ \ $ – Bill Dubuque Jan 25 '23 at 00:08

1 Answers1

0

Yes, that works. However, for large values of $8$ it will be MUCH slower than the Euclidean algorithm.

Igor Rivin
  • 25,627
  • 1
  • 18
  • 40