Is there a simpler way to find an inverse of a congruence?

Question

In order to find an inverse of a congruence, do we have to go through Euclid’s algorithm and do back substitution?

Here is an example to find an inverse of 9 modulo 23.

Answer 1

EDIT: remembered the name of the thing I was talking about: the primitive roots

My two favorite methods are guessing and brute-forcing. Together with Euclid's Algorithm, these are the most pratical ways I know of calculating inverses.

(As I see now from other answers there are many inventive representations and ways to compute just a couple of useful methods.)

Unless one knows a primitive root, in which case it generates all invertible elements and therefore inverting one is just check what is the power of the primitive root that cancels it.

Answer 2

Here's another method. Maybe you could still call it Euclid's algorithm though. Subtract consecutive equations:

$$23=23(1)+9(0)\\ 9=23(0)+9(1)\\ 5=23(1)+9(-2)$$

(Here $23-9\cdot 2= 5$)

$$4=23(-1)+9(3)\\1=23(2)+9(-5)$$

$$9(-5)\equiv 1\pmod{23}\\ 9^{-1}\equiv -5\equiv 18\pmod{23}$$

Answer 3

This is the (simple) continued fraction for 23/9. It is the same as Euclid but I find this way of going about it much easier to remember.

the first "digit" is $23/9 \approx 2.555$ We record the integer part, $2,$ then take the reciprocal of the fractional part, until we get an integer: $$ 2.555555556, \; 1.799999999, \; 1.250000002, \; 3.999999968$$ where we believe the 3.999999968 is really 4, integral digits $$ 2, 1, 1, 4. $$

Given two consecutive fractions "convergents," we just take the top of the first plus the new digit (integer) times the second, same for the bottoms (denominators. Easy. With two consecutive convergents, the cross product is $\pm 1.$

$$ \begin{array}{cccccccccccccccccccccccccccccc} & & & 2 & & 1 & & 1 & & 4 & \\ \frac{0}{1} & & \frac{1}{0} & & \frac{2}{1} & & \frac{3}{1} & & \frac{5}{2} & & \frac{23}{9} & \end{array} $$

$$ 5 \cdot 9 - 23 \cdot 2 = -1 $$ $$ -5 \cdot 9 + 23 \cdot 2 = 1 $$

Here is another example, you could say to find the inverse of $200 \pmod{567}$

$$ \begin{array}{cccccccccccccccccccccccccccccc} & & & 2 & & 1 & & 5 & & 16 & & 2 \\ \frac{0}{1} & & \frac{1}{0} & & \frac{2}{1} & & \frac{3}{1} & & \frac{17}{6} & & \frac{275}{97} & & \frac{567}{200} \end{array} $$ with the final two by two cross product $$ 275 \cdot 200 - 567 \cdot 97 = 1. $$ For illustration, note that $$ 17 \cdot 97 - 275 \cdot 6 = -1. $$

I'm going to type in the example in https://en.wikipedia.org/wiki/Continued_fraction#Calculating_continued_fraction_representations

$$ 3.245, \; 4.081632653, \; 12.25000001, \; 3.999999840 $$ where we believe the 3.999999840 is really 4, integral digits $$ 3, 4, 12, 4. $$

$$ \begin{array}{cccccccccccccccccccccccccccccc} & & & 3 & & 4 & & 12 & & 4 & \\ \frac{0}{1} & & \frac{1}{0} & & \frac{3}{1} & & \frac{13}{4} & & \frac{159}{49} & & \frac{649}{200} & \end{array} $$

One thing this shows is that $3.245 = 649/200.$ Also, $159 \cdot 200 - 649 \cot 49 = -1.$ That is, if you began looking for an inverse of $1000 \pmod {3245},$ this is what you would get, since there is a common factor 5.

Found a place where the wikipedia article shows convergents the way I like to write them:

Answer 4

There are many ways to compute modular inverses that are often simpler for smaller numbers, e.g. below I use Gauss's algorithm a few ways. The basic idea is to scale the top and bottom to obtain a $\rm\color{#c00}{smaller}$ denominator, then repeat, till the bottom exactly divides the top (or $ $ top $\!\pm\!$ modulus)

${\rm mod}\ 23\!:\,\ \dfrac{1}9\equiv \dfrac{3}{27}\equiv \dfrac{-20}{\color{#c00}4}\equiv -5$

${\rm mod}\ 23\!:\,\ \dfrac{1}9\equiv \dfrac{2}{18}\equiv \dfrac{25}{\color{#c00}{-5}}\equiv -5$

${\rm mod}\ 23\!:\,\ \dfrac{1}3\equiv \dfrac{24}3\equiv 8\,\Rightarrow\,\dfrac{1}9\equiv 8^2\equiv -5 $

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

Answer 5

You can use the Euler Theorem/Fermat Little Theorem:

By Euler Theorem

$$a^{\phi(n)-1}\equiv a^{-1} \pmod{n}$$

The LHS can be calculate by doubling the power usually fast, but for large $n$ it is not as fast as the Euclidian algorithm.

If $p$ is prime we get $$a^{-1} \equiv a^{p-2} \pmod{p}$$

With your example we get $$9^2 \equiv 81 \equiv 12 \pmod{23} \\ 9^4 \equiv 144 \equiv 6 \pmod{23} \\ 9^8 \equiv 36 \equiv -10 \pmod{23} \\ 9^{16} \equiv 100 \equiv 8 \pmod{23} \\ 9{-1} \equiv 9^{21} \equiv 9^{16}\cdot 9^4 \cdot 9^1 \equiv 8 \cdot 6 \cdot 9 \equiv 2 \cdot 9 \equiv 18 \equiv -5 \pmod{23}$$

P.S. In this exercise it is much faster to find the inverse of $3 \pmod{23}$ by the Euclidian algorithm and square it.

Answer 6

Okay, this is kind of a modified Euclid algorithm/Gauss algorithm combo.

$1/9 \mod 23$. I want to get a smaller denominator and eventually a denominator of 1. I note that if $23 = k*9 \pm d; d < 9$, I can get $\frac 19 = \frac k{9*k} = \frac k{23 \mp d} \equiv \frac kd \mod 23$ will have a smaller denominator.

So $23 = 27 - 4 = 3*9 - 4$. So $\frac 19 = \frac {3}{27} \equiv \frac 34 \mod 23$.

Now $23 = 4*6 -1$ so $\frac 34 = \frac {18}{24} \equiv {-5}{1} \mod 23 = -5 \mod 23$. (Or $18 \mod 23$. Both are acceptable $18 \equiv -5 \mod 23$.)

====

Your other example $\frac 1{8400} \mod 11$ will require noting that as $8400 > 11$ we can reduce it to $8400 \equiv 7 \mod 11$ so

$\frac 1{8400} \equiv \frac 17 \mod 11$

So $11 = 7 + 4$, $\frac 17 \equiv -\frac 14 \mod 11$.

And $11 = 3*4 - 1$, $-\frac 14 = -\frac 3{12} \equiv -\frac 3{1} \equiv -3 \mod 11$. (And $8 \equiv -3 \mod 11$ so also acceptable.)

===

To do a hard one with a pitfall:

$\frac 1{63} \mod 200$

$200 = 3*63 + 11$ so $\frac 1{63} = \frac{3}{189} \equiv -\frac{3}{11}$.

$200 = 20*11 -20$ !!BUT!! this will not be acceptable as $gcd(20,200) \ne 1$ so we can NOT use this.

$200 = 19*11 - 9; 200 + 9 = 19*11$ which is smaller anyway.

So $-\frac{3}{11} = -\frac{3*19}{19*11}\equiv -\frac{57}9$.

And $-\frac{57}{9 } = -\frac{19}{3}$.

And $200 = 201 - 1 = 3*67 - 1$.

So $-\frac{19}{3} = -\frac {19*67}{201} \equiv -19*67 = -[20*67 - 67] \equiv -[7*20 -67]= -[140 -67]=-73 \mod 3$.

And indeed $63*(-73) = -4599 = -4600 + 1\equiv 1 \mod 200$.