# Multiple Exponentiation in Modular Arithmetic [duplicate]

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.

• Checking this post might be useful: How do I compute $a^b\,\bmod c$ by hand? – Martin Sleziak Mar 11 '19 at 18:34
• Not a dupe of the listed generic thread. Please don't vote to close. – Bill Dubuque Mar 11 '19 at 22:02
• Dupe closures should not be abused by sending askers on possible wild goose chases (that may or may not be successful). That generic thread is a motley mix of unrelated techniques. It is far from complete, and (pedagogical) quality leaves much to be desired. If one has the (extensive) number theory background required to know for sure that some answer(s) there cover all the ways one would attack some question then one should specifically link to said answers (and elaborate on how they apply if need be) – Bill Dubuque Mar 11 '19 at 22:03
• Problems of this sort can be solved using all sorts of number theory, group theory, linear algebra. etc. They are posed not for the purpose of getting an answer but, rather, to expose students to the diverse techniques in number theory and algebra that can be used in their solution (similar to integration problems in calculus). One can use them to motivate and illustrate many major topics in number theory (e.g. euclidean algorithm, quadratic reciprocity, (cyclic) group theory, Euler, Fermat and Carmichael theorems, Chinese Remainder Theorem and lifting the exponent and related p-adic ideas – Bill Dubuque Mar 11 '19 at 22:03

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

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

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