I am looking for the modulo inverse of the following large exponential number that also has a large modulo:
$21^{10^{18}}$ mod $10^9$ + 7
I use the Euler's theorem: $a^{-1}$ mod n $\equiv$ $a^{\phi(n) – 1}$ mod n where $\phi(n)$ is the Euler's totient function.
Since n is a prime number in our case, $\phi(n) = n-1 $. Therefore, $\phi(10^9+7)$ = $10^9$ + 6
$(21^{10^{18}})^{-1}$ mod $10^9+7$ $\equiv$ $(21^{10^{18}})^{{10^9+6}-1}$ mod $10^9$ + 7
RHS = $(21^{10^{18}})^{10^9+5}$ mod $10^9$ + 7
I do not know how to further reduce the above large exponent. Any help is greatly appreciated!
Best Answer
There are ways to reduce this to a $\rm\color{#90f}{handful}$ of multiplications $\!\bmod p = 10^9+7.\,$ First, notice that $\!\bmod p\!-\!1 = 10^9+6\!:\ \color{#0a0}{10^9\equiv -6}\Rightarrow 10^{18}\equiv(\color{#0a0}{10^9})^2\equiv (\color{#0a0}{-6})^2\equiv 36,\,$ so by mod order reduction $\!\bmod p\!:\ 21^{10^{18}}\equiv 21^{36}$ has inverse $(1/21)^{36}.\,$ But it is very easy to compute inverses of small numbers like $21$ by employing the handy method $\,\rm\color{#c00}{IR} =$ inverse reciprocity, i.e.
$$\qquad\begin{align} \bmod 3\!:\,\ &p\equiv 1^9+1\equiv -1\\[.4em] \bmod 7\!:\,\ &p\equiv 3^9+0\equiv -1,\,\text{ by }\ 3^6\equiv 1\\[.3em] \overset{\rm\small CCRT}\Longrightarrow\ \bmod 21\!:\,\ &p\equiv \color{c00}{-1},\text{ thus }\bmod p\!:\ \dfrac{1}{21}\overset{\rm\color{#c00}{IR}}\equiv \dfrac{1+p}{21}\equiv 47619048 =: c \end{align}$$
so repeated squaring (a $\rm\color{#90f}{handful}$ of multiplications) $\,\Rightarrow\, \left[\dfrac{1}{21}\right]^{36}\!\!\!\equiv c^{36}\equiv 753568836\,$
viz. $\,c^{\large 36} = (c^{\large 2}c^{\large 2^{\Large 4}})^{\!\large \,2},\,$ via $\color{#90f}{\text{5 squarings + 1 multiplication}}$.