Finding $2^{-1}\pmod{53}$ via Euclidean algorithm

95 Views Asked by At

A quick way of finding the inverse is to notice that $27\times2\equiv54\equiv1\pmod{53}$, so $2^{-1}\equiv27\pmod{53}$.

However, I'm trying to arrive at the same result by resorting to the EA. My process is as follows:

$$53=2\times25+3$$ $$25=3\times8+1$$ $$\implies1=25-8\times(53-2\times25)=17\times25+(-8)\times53$$

But taking both sides modulo $53$ only seems to tell me that $17$ and $25$ are inverses, which is correct. In my limited experience with more involved exercises in solving $ax\equiv 1\pmod n$ (i.e. no "eyeball" tricks), I'm under the impression that the last step in the algorithm must always return a tractable result; in other words, I expected to get an equation like

$$\implies 1=2\times 27\pm53k$$

or

$$\implies 1=2\times (-26)\pm53k$$

etc. in which, taken modulo $53$, I immediately get the inverse of $2$. What gives? Am I getting the wrong impression? Did I make a mistake somewhere, or is there more manipulation that needs to be done?

1

There are 1 best solutions below

1
On BEST ANSWER

In your lines $\;3-6\;$ you seem to have forgotten that you want $\;2^{-1}\;$ ...:

$$53=2\cdot26+1\implies1=53+2\cdot(-26)\implies 2^{-1}=-26=27\pmod{53}$$

Among other things: in your first line of calculations, the residue must be less than $\;2\;$ ...and it isn't.