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.