Finding the inverse modulo of a large exponent that has a large modulo

Question

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!

Answer 1

Let $p = 10^9 + 7$. Euler's theorem (the same one you cited) tells us $21^{p-1} \equiv 1 \mod p$. Thus when raising $21$ to some huge power, we can reduce that exponent mod $p-1$ without changing the final result. It turns out that $10^{18} \equiv 36 \mod (p-1)$, so $21^{10^{18}} \equiv 21^{36} \mod p$, and the modular inverse of $21^{10^{18}}$ will be the same as the modular inverse of $21^{36}$.

Next we should use the same method you were starting to try before. The inverse of $21^{36}$ mod $p$ will be $\left(21^{36}\right)^{p-2}$ mod $p$.

From here, we could brute force the answer using $p-2$ multiplications on a computer, but $10^9$ operations may take awhile depending which language you use. Instead, we can speed up the process using the exponentiation by squaring algorithm, which lets us use around $\log_2(p)$ operations instead of $p$ operations.

Here's a short Python script that puts all these steps together.

p = 10**9 + 7
e = 10**18 % (p-1)  # aka 36
b = pow(21, e, p)  # b is 21^(10^18) mod p
result = pow(b, p-2, p)
print(result)

The final answer returned is 753568836. Note that in Python, pow(x, y, z) means $x^y \mod z$, and it runs fast because it incorporates "exponentiation by squaring" (or something similar). The code runs instantly on my laptop.

Answer 2

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}}$.