Calculation of modular multiplicative inverse of A mod B when A > B

Question

I'm trying to understand a Montgomery reduction algorithm, for which I need to calculate a multiplicative inverse. However, Euclidean algorithm only helps if $A < B$.

Example is $11 \mod 3$. Multiplicative inverse of $11$ is $2$,but ext_gcd gives you Bezout numbers such as -1 and 4.

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Wikipedia says so:

The extended Euclidean algorithm is particularly useful when $a$ and $b$ are coprime, since $x$ is the modular multiplicative inverse of $a$ modulo $b$, and $y$ is the modular multiplicative inverse of $b$ modulo $a$.

But as far as I see, this can't be true, either $X$ is multiplicative inverse of $A$ modulo $B$ or $Y$ is multiplicative inverse of $B$ modulo $A$, but not both at the same time, because one of them ($A$ or $B$) is going to be bigger than another. We have $X=4, Y=-1$ for $A=3,B=11$, and $X=4$ is valid inverse, while $-1$ is indeed not.

A lot of online calculators that I tried are also said that a has to be bigger than be, but they (some of them) are still able to calculate inverse of $11 \mod 3$.

The only workaround I found so far is perform $A = A \mod B$ first, so $A$ is now a remainder of divisions and therefore is less than modulus, so we can perform ext_gcd(2, 3) now and get our $2$ as answer.

Probably I'm missing something, this thing is pretty new for me.

Thanks.

Answer 1

It is inevitable that a Bézout's identity equation will give you modular multiplicative inverses, since given:

$$am+bn = 1$$

we can take $\bmod m$ for

$$ bn\equiv 1 \bmod m$$

or $\bmod n $ for

$$ am \equiv 1 \bmod n$$

To get $a$ and $b$ in your preferred range, you can simply add or subtract a suitable multiple of the modulus.

So in this case $$-1\cdot 11 + 4\cdot 3 = 1$$

and thus $$-1\cdot 11\equiv 1 \bmod 3$$

($-11$ being one more than $-12$), so $-1$ is a valid inverse of $11$ modulo $3$. Then of course $$-1\equiv 2 \bmod 3$$

so this is consistent with your observation that $2$ is the inverse of $11 \bmod 3$ also.

Answer 2

$-1 \equiv 2 \mod 3$ so they are considered to be the same thing.

That's we we call these equivalence classes.

However, euclidean algorithm only helps if A < B

I simply do not understand why you say that.

either X is multiplicative inverse of A modulo B or Y is multiplicative inverse of B modulo A, but not both at the same time, because one of them (A or B) is going to be bigger than another. We have X=4, Y=-1 for A=3,B=11, and X=4 is valid inverse, while -1 is indeed not.

Except, of course, it indeed is. $-1*11 = -11 \equiv 1 \mod 3$. That is the valid inverse. Why do you think it is not?

It doesn't matter if $A > B$ or $B> A$ as $\gcd(A,B) = 1$ Euclid's algorithm will give us:

$mA + kB = 1$ so $k \equiv A^{-1} \mod B$ and $m \equiv B^{-1} \mod A$ simultaneously.

Is your concern that one is represented with a positive number and the other negative?

That's irrelevent.

It doesn't matter which representative we use to represent a class. We could have used $50\equiv -1 \mod 3$ so $50 \equiv 11^{-1}\mod 3$ for all we care. (Indeed $50*11 = 550 = 3*183 + 1 \equiv 1\mod 3$).

Note: if $mA + kB = 1$ and $m > 0$ but $-A < k < 0$ then

$mA + (k+A)B = 1 + BA\equiv 1 \mod A,B,AB$ and $m$ and $(k+A)$ are still the proper inverses. ANd $m > 0; k+A > 0$.

Indeed $(m + vB)A + (k + uA)B = 1 + (v+u)AB$ so $m + vB\equiv A^{-1} \mod B$ for any integer $v$ and $k + uA \equiv B^{-1} \mod A$ for any integer $u$.