Fdtxjr

There is an answer on the site for solving simple linear congruences via so called 'Gauss's Algorithm' presented in a fractional form. Answer was given by Bill Dubuque and it was said that the fractional form is essentially Gauss, Disquisitiones Arithmeticae, Art. 13, 1801.

Now I have studied the article from the book, but I am not seeing the connection to the fractional form. What Gauss does is reducing $b$ via $pbmod b= p - qb$ and I do not see that happening in the fractional form nor do I see how it computes an inverse. I have already talked with Bill about this via comments, but decided to open a new question so he or anyone else can help me more intuitively understand what is going on here. This article is supposed to give an algorithm to compute inverses in a prime modulus, yet I have no idea how.

Edit:

Actual question for Bill:

I may have been asking some stupid questions up till now so I will give something concrete and hopefully you can provide an answer to that.

Let's take your sci.math example for this:

So we are looking for a multiplicative inverse $x$ of $60$ in modulo $103$

$$60x equiv 1 pmod103$$

The tool we can use for this is, as Bill has said, a special case of the Euclidean algorithm which iterates $(pbmod b,, p)$ instead of the usual Euclidean algorithm that iterates $(p bmod b,, b)$.

This is the result of that algorithm:

$$103=60 cdot color#c00 1 + 43 = 43 cdot color#c002 + 17 = 17 cdot color#c00 6 + 1$$

And then this translates into the following in mod $103$:
$$60 cdot color#c00(-1) equiv 43 rightarrow 43 cdot color#c00(-2) equiv 17 rightarrow 17 cdot color#c00(-6) equiv 1$$

Producing the numbers in red which when multiplied give an inverse:

$$60 cdot color#c00(-1)(-2)(-6) equiv 1 pmod103$$
$$x equiv-12 pmod103$$

And this is fine and I see it works, of course only when the number and modulo are coprime.

Now my question is why this works. I am not interested in optimisations and different ways of reaching the inverse, but specifically why do the same values of the numbers in red(the coefficients of the algorithm descent) produce an inverse? This method of reusing the coefficients does not work via the normal Euclidean algorithm, but only with this special case. What is special about this? I would like to see a generalized proof or reason as to why the generated numbers produced via this special algorithm have this property.

Below we compare the related forms. First is the iterated descent $,ato 103bmod a,$ used by Gauss. Second is that rearranged into the form of descending multiples of $60.,$ Third is the fractional view, and fourth is the graph of the descending multiples of $60$ (denominator descent graph).

$$beginalign
103bmod60 &= 103 - 1(60) = 43\
103bmod 43 &= 103color#0a0-2(43)=17\
103bmod 17 &= 103-6(17) = 1
endalignqquadqquadquad$$

$$beginarrayrl
bmod103!:qquad (-1)60!!!! &equiv, 43 &Rightarrow 1/60equiv -1/43\[.3em]
smash[t]oversetlargecolor#0a0*(-2)Longrightarrow (-2)(-1)60!!!! &equiv color#0a0(-2)43equiv 17!! &Rightarrow 1/60equiv 2/17\[.3em]
smash[t]oversetlarge *(-6)Longrightarrow color#c00(-6)(-2)(-1)60!!!! &equiv (-6)17equiv 1 &Rightarrow 1/60 equiv color#c00-12/1\
endarray$$

$$ beginalign
&dfrac160 ,equiv dfrac-143, equiv, dfrac217, equiv, dfraccolor#c00-121 rm[Gauss's algorithm]\[.3em]
&, 60oversetlarge *(-1)longrightarrowcolor#0a043oversetlargecolor#0a0*(-2)longrightarrow,color#0a017oversetlarge *(-6)longrightarrow 1\[.4em]
Rightarrow &,60*(-1)color#0a0*(-2)*(-6)equiv 1
endalign$$

The translation from the first form (iterated mods) to the second (iterated smaller multiples) is realized by viewing the modular reductions as modular multiplications, e.g.

$$ 103color#0a0-2(43) = 17,Rightarrow, color#0a0-2(43) equiv 17!!pmod!103 $$

This leads to the following simple recursive algorithm for computing inverses $!bmod p,$ prime.

$beginalignrm I(a,p) := &rm if a = 1 then 1qquadqquad ; a^-1bmod p,, rm for a,pinBbb N, &, 0 < a < p prime \[.5em]
&rm else let [,q,,r,], =, p div aqquad ;, p = q a + r Rightarrow color#0a0-qa,equiv, r!!pmod!p, 0 < r < a,\[.2em]
&rm (-q*I(r,p))bmod p ; because dfrac1a equiv dfrac-qcolor#0a0-qaequiv dfrac-qcolor#0a0requiv -q * I(r,p) color#90f[![1]!] endalign
$

Theorem $ I(a,p) = a^-1bmod p$

Proof $ $ Clear if $,a = 1.,$ Let $,a > 1,$ and suppose for induction the theorem holds true for all $,n < a$. Since $,p = qa+r,$ we must have $,r > 0,$ (else $,r = 0,Rightarrow,amid p,$ and $,1< a < p,,$ contra $,p,$ prime). Thus $,0 < r < a,$ so induction $,Rightarrow,I(r,p)equiv color#0a0r^-1$ so reducing equation $color#90f[![1]!]bmod p,$ yields the claim.

I'm not sure I've properly understood what you're looking for, but since the reason why the algorithm works seems to me to be patently clear from the formal proof that it does, in fact, work, here's such a proof for the general case.

Starting with a prime $ p $, and an integer $ b_0in left[1, pright] $, the algorithm successively produces integers $ b_1<b_0,b_2<b_1, dots, b_i+1 < b_i, dots $, with $ b_i+1 equiv -q_i b_i left(,mathrmmod p,right) $, until it obtains $ b_n = 1 $. As long as $ b_i notinleft0, 1right $, it's always possible to carry out the next step of the procedure by using the division algorithm: $ p = q_i,b_i + b_i+1 $, and since the sequence $ b_0, b_1, dots b_i, dots $ is strictly decreasing, the algorithm must eventually terminate with $ b_ninleft0, 1right $. If $ b_n $ were $ 0 $, however, the final step of the algorithm would have been $ p = q_n-1,b_n-1 + b_n = q_n-1,b_n-1 $, whence $ b_n-1 $, strictly smaller than the prime $ p $, would be a divisor of it, and hence equal to $ 1 $. Thus, the algorithm would have terminated on the preceeding step.

Thus the algorithm always terminates with $ b_n=1 $, and we then have begineqnarray
1&equiv& -q_n-1,b_n-1equiv q_n-1,q_n-2,b_n-2equivdots\
&equiv& left(-1right)^n,q_n-1,q_n-2dots q_0,b_0 left(,mathrmmod,p,right) endeqnarray.