2
$\begingroup$

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. enter image description here

$\endgroup$
  • $\begingroup$ You have the extended Euclidean algorithm which gives directly the gcd and the Bézout's coefficients, hence the modular inverse. Please see my answer to this question for an example with the standard layout, and my answer to this other question for a sketch of the justification. $\endgroup$ – Bernard Nov 24 '16 at 0:07
  • $\begingroup$ You can avoid the tedious error-prone back-substitution in the extended Euclidean algorithm by instead using this more convenient version of the algorithm. $\endgroup$ – Bill Dubuque Nov 24 '16 at 0:19
  • $\begingroup$ I dunno. Common sense says 23 = 3x9 -4. so $1/9 = 3/27 = 3/4. 23 =6*4 -1$. So $3/4 = 18/24 = 18$. Its basically euclids algorithm but without needing to keep a tally. Harder example 1/27 mod 103. 1/27=4/108 = 4/5 = 84/105= 84/2=42. Check... $27*42 = 1134=1133 + 1 = 103x11 + 1$. Yep. Seems to work. $\endgroup$ – fleablood Nov 24 '16 at 0:29
  • $\begingroup$ @fleablood Does your final answer is 18? If so, then there maybe some mistakes in your method. The inverse should be 8. $\endgroup$ – yashirq Nov 24 '16 at 0:50
  • $\begingroup$ Why do you think it should be 8? All the answers so far universally (!including the one in the text!) say it is -5 = 18. 9x-5 = -45 = 1 mod 23 and 9x18 = 162 = 7*23 + 1 = 1 mod 23. But 8*7 = 72 = 3 mod 23. I think I'm right. $\endgroup$ – fleablood Nov 24 '16 at 1:07
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, guessing is a good idea(not kidding). But it seems not a good way for those larger numbers. Like $8400^–1 (mod 11)$, how are you going to guess? $\endgroup$ – yashirq Nov 23 '16 at 23:56
  • $\begingroup$ @yashirq one first reduces $8400$ to $-400$ (take 8800) then to $40$ (add 44) and then to $7$. Now try to guess 7's inverse. $\endgroup$ – RGS Nov 23 '16 at 23:58
  • $\begingroup$ Nice one. It still count upto 8. OMG-.- $\endgroup$ – yashirq Nov 24 '16 at 0:08
  • $\begingroup$ 8400 = 4000 + 4400 = 667 + 3333 + 4400 = 7 + 660 + 3333 + 4400. So 8400 = 7 mod 11. so 1/8400 mod 11 = 1/7 mod 11 = (1+55)/7 mod 11 = 56/7 = 8. And indeed 8x8400 = 67200 = 67199 +1 = 6109x11 + 1. $\endgroup$ – fleablood Nov 24 '16 at 1:24
  • $\begingroup$ For your last paragraph you would have to solve the discrete-log problem which is not known to have a polynomial-time deterministic algorithm (but it has a polynomial-time quantum algorithm developed by Shor; see en.wikipedia.org/wiki/Discrete_logarithm). $\endgroup$ – user21820 Nov 25 '16 at 6:49
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't quite understand. For the first line, how do you get $-20/4$? I mean, why it can't be $-30/6$ or others. And for the third line, why it becomes $1/3$? We were doing $1/9$ $\endgroup$ – yashirq Nov 24 '16 at 0:23
  • $\begingroup$ @yashirq Gauss's algorithm is explained in the link. We multiply $\,9\,$ by $\,3\,$ since this yields $27\equiv 4$, a smaller denominator $\, 4 < 9.\,$ Or we could multiply $\,9\,$ by $2$ yielding $18\equiv -5,\,$ which is also smaller $\ |-5| < 9.\ \ $ $\endgroup$ – Bill Dubuque Nov 24 '16 at 0:27
  • $\begingroup$ 1/9 = 3/27 = (23 -20)/(23 + 4) $\equiv$ -20/4. How do you figure -30/6? It's arbitrary which direction we go. We could probably get -30/6 somehow. 1/9 = 16/144 = (-30+2*23)/(6*23 + 6) $\equiv$ -30/6 = -5 would work. But it's not intuitive. $\endgroup$ – fleablood Nov 24 '16 at 1:15
  • $\begingroup$ @fleablood I don't understand your question. It is an algorithm, Do you not understand how the scaling factor is chosen so that the denominator $\,d\,$ is scaled to the smaller value $\,-p\bmod d,\,$ where $\,p\,$ is the modulus. That is explained in the link. $\endgroup$ – Bill Dubuque Nov 24 '16 at 1:45
  • 1
    $\begingroup$ I never said the algorhithm properly applied would yield -30/6. I was answering the question "why -20/4 rather than -30/6". -30/6, if you were to somehow come up with it (which you could be perversely choosing to mulptiple num and denom by 16). You never in you post explained why you choose to multiply by2 or 3, and not 16 (although your comment above explains). I was trying to show that there was no magic in one guess being right and the others being wrong (although there is a matter of some being more efficient). $\endgroup$ – fleablood Nov 24 '16 at 18:03
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is the Euclid's algorithm under cover :p $\endgroup$ – RGS Nov 23 '16 at 23:48
  • $\begingroup$ @user236182 Yea, this is the way I did before. It is tedious. $\endgroup$ – yashirq Nov 23 '16 at 23:50
  • $\begingroup$ @yashirq This linear algebra form of the extended Euclidean algorithm is described at length in this answer. It is much less tedious than the standard method with back-substitution. And there are various optimizations, e.g. eliminating one column and/or using fractions. Generally it will yield the most efficient approach. The methods in the answer you accepted ("guessing" or using primitive roots), will fail miserably in general, so it's not clear why you found that acceptable. $\endgroup$ – Bill Dubuque Jan 3 '17 at 16:13
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ Can you explain a bit what are those 2 lists of numbers? $\endgroup$ – yashirq Nov 23 '16 at 23:52
  • $\begingroup$ Cool. I'll try to figure it out after finished my assignment. $\endgroup$ – yashirq Nov 24 '16 at 4:04
  • $\begingroup$ Why do you get 1/(1.25-1) = 3.999999??? $\endgroup$ – user21820 Dec 4 '16 at 5:47
  • $\begingroup$ @user21820, I did not type in the full numbers from my hand calculator. In full, $$ 2.555555556, \; 1.799999999, \; 1.250000002, \; 3.999999968$$ $\endgroup$ – Will Jagy Dec 4 '16 at 17:32
  • $\begingroup$ Oh okay. But why did you use a hand calculator when you can do it by hand?! And get exact answers with your head? $\endgroup$ – user21820 Dec 5 '16 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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