Multiple Exponentiation in Modular Arithmetic

Question

I need to solve $18^{19^{20}} \mod21$ and problems like it without a calculator. I believe there is a way to decompose this into a problem solvable with Fermat's little theorem. I just can't figure out how.

Answer 1

Clearly $18^{19^{20}} \equiv 0\ (\text{mod }3).$ By Fermat's little theorem, we have $18^6\equiv 1\ (\text{mod }7)$ and $19^{20}\equiv 1^{20}=1\ (\text{mod }6)$. If we write $19^{20}=6N+1$, we then have $$ 18^{19^{20}} \equiv18^{6N+1} \equiv (18^6)^N18\equiv 18 \ (\text{mod }7). $$ By chinese remainder theorem, this gives $$ 18^{19^{20}}\equiv 18 \ (\text{mod }21). $$

Answer 2

$\color{#c00}{J\equiv1}\pmod{\!\color{#c00}6}$ $\ \Rightarrow\,\bmod 21\!:\ (3a)^{\large J^{\Large K}}\!\!\equiv 3 \overbrace{\left[\dfrac{(3a)^{\color{#c00}{\large J}^{\Large K}\!\!\!\!}}3\!\bmod 7\right]}^{\large \bmod{\color{#c00} 6}:\ \ \color{#c00}{J}^{\Large K}\ \equiv\ \color{#c00}1^{\Large K} \ \ }\! \equiv 3a\,\ $ by little Fermat

Remark $ $ We used $\ \bmod cn\!:\ cb \equiv c(b \bmod n),\ $ the mod Distributive Law. Note that above congruence is trivially true (has form $\,0^N\equiv 0)$ if $\,7\mid a\,$ so we can restrict to $\,7\nmid a$ for Fermat.

More generally it is the special case $\,p,q,e,f = 3,7,1,J^K\!-1\,$ of the following

Lemma $\,p\neq q\,$ primes and $\, \color{#c00}{p\!-\!1,\,q\!-\!1\mid k}\ $ $\Rightarrow\, pq\mid a^e(a^f\!-\!1)\,$ for all $\,a\,$ and $\,e>0$

This generalizes further as below. See this answer for proofs and examples.

Theorem $\ $ Suppose that $\ m\in \mathbb N\ $ has the prime factorization $\:m = p_1^{e_{1}}\cdots\:p_k^{e_k}\ $ and suppose that for all $\,i,\,$ $\ e\ge e_i\ $ and $\ \phi(p_i^{e_{i}})\mid f.\ $ Then $\ m\mid a^e(a^f-1)\ $ for all $\: a\in \mathbb Z.$

Answer 3

Think of it as bootstrapping.

If $a,n$ are relatively prime then $a^{\phi n} \equiv 1 \pmod n$. So $a^{k}\equiv a^{m}\pmod n$ if $k\equiv m \pmod \phi(n)$. And so solving $a^{b^c} \pmod n$ is a matter of solving $b^c \pmod {\phi(n)}$ and if $b, \phi (n)$ are relatively prime this is a matter of solve $c \pmod {\phi(\phi n)}$ and we can boot strap this forever.

But if they aren't relatively prime we may have to bring in Chinese remainder theorem.

$\gcd (18, 21)=3$ so break this to i) $x \equiv 0 \pmod 3$ and ii) $x \equiv 18^{19^{20}} \pmod 7$.

And ii) is a matter of $19^{20} \pmod {\phi(7) = 6}$.

And as $19 \equiv 1 \pmod 6$ we don't have to do much more. $19^{20} \equiv 1 \pmod 6$ so $18^{19^{20}}\equiv 18^{1}\equiv 4 \pmod 7$.

So we have to solve $x \equiv 0 \pmod 3$ and $x \equiv 4 \pmod 7$ to get $18^{19^{20}} \equiv x \pmod {21}$ and well, we .... really don't have to do much as we started with $18 \equiv 0 \pmod 3$ and $18 \equiv 4 \pmod 7$.