Complexity of the inverse modulo a composite number
Let us call the function which takes $(a,b)$ to $r$ such that $a = bq + r$ with $r &lt; b$ (and all of $a,b,q,r$ nonnegative integers) the Remainder function. This function cannot be computed at all using only ring operations in the integers: any function that can be computed using only ring operations is a polynomial of its inputs, so if the Remainder function could be computed using only ring operations, it would follow that $Remainder(a,b) = f(a,b)$ for some integer polynomial $f$. For any fixed $b &gt; 1$, the function $g(x) = f(x,b)$ would then be a univariate polynomial. Now, $g(b+1) = 1$, so $g(x)$ is not identically zero; but $g(x) = 0$ whenever $b | x$, so $g(x)$ has infinitely many zeroes, a contradiction.

However, if you allow $&lt;$ in addition to ring operations, then the Remainder function can be computed in polynomially many steps (in the number of bits of the input) as follows: start with $q=1$ and check if $qb &gt; a$ (if so, then the remainder is just $a$). Otherwise, multiply $q$ by $2$ repeatedly until $qb &gt; a$. Then do binary search on $q$ to find $q$ such that $qb \leq a$ and $(q+1)b &gt; a$, and finally output $a - bq$. This takes $O(\log (a/b))$ ring operations and comparisons; on most standard Boolean models of computation each such operation can be done in nearly $O(\log a)$ time.