Shortcut to find remainder (mod) of a number to a negative power?

Question

How would one find the remainder to a question of the type $a^{-x} / b$ really fast?

Came across this situation while solving the remainder of $12^{107} / 37$

Using Fermat's little theorem we get $12^{108} \mod 37 = 1$ which would mean the question is nothing, but the remainder of $(12^{-1} \times 12^{108} ) / 37 \implies 12^{-1} \times 1 / 37$ (Basic remainder theorem)

Is there an easy and fast method to solving this question from this step?

I did manage to solve it but with 4 additional steps, where I basically got the numerator to a 3-digit value applying Fermat's and basic remainder theorem multiple times. But in a competitive time crunch exam situation, I do not think my method is ideal, there must be a way to easily solve $12^{-1} \mod 37$ fast.

Answer 1

What you want is the answer to $$a\equiv 12^{-1}\pmod{37}$$ or equivalently, on multiplying through by $12$ to $$12a\equiv 12\cdot12^{-1}\equiv1\pmod{37}$$ where $a$ is the inverse of $12$ modulo $37$.

Now by Fermat's Little Theorem we have: $$12^{37-1}=12^{36}\equiv1\pmod{37}$$ On noting $12a\equiv 12^{36}\pmod{37}$ we have, on dividing through by $12$, that
$$a\equiv 12^{35}=(12^{5})^{7}=248832^7\equiv 7^{7}=823543\equiv34\equiv-3\pmod{37}$$ So $a\equiv-3$ is the answer.

Answer 2

It is trivial to invert a number that divides modulus $\pm 1,\,$ e.g. here $\,12\mid 37-1,\,$ i.e $\,3\cdot 12 = 37-1\,$ so $\,{\rm mod}\ 17\!:\,\ 3\cdot 12\equiv -1\,$ so $\,12^{-1}\equiv -3.\ $ Said in fraction language

$$\dfrac{1}{12}\equiv \dfrac{-36}{12} \equiv \dfrac{-3}{1}$$

This is essentially an optimzation of the extended Euclidean algorithm (when it terminates in one or two steps). There are other ad-hoc methods that are best expressed in terms of fraction arithmetic (e.g. using factorizations, cancellation, etc), e.g. see some of my prior posts using modular fractions