How to find out a^b^c^… mod m

Question

I would like to calculate:

a^bcd... mod m

I know when a is coprime to m then we can easily find out the answer using Euler's totient function. But I wish to know the ideas when a is not coprime to m.

Thanks In Advance !!!

Answer 1

Use Chinese Remainder Theorem. We have

$$\begin{cases}m=\gcd(a,m)\cdot m_1\\a=\gcd(a,m)\cdot a_1\\ m_1,a_1\in\mathbb Z\end{cases}$$

$$\begin{cases}a^{b^{c^{d^\ldots}}}\equiv 0\pmod {\gcd(a,m)}\\ a^{b^{c^{d^\ldots}}}\equiv a^{b^{c^{d^\ldots}}\mod {\phi(m_1)}}\equiv r \pmod{m_1}, r\neq 0\end{cases}$$

$$a^{b^{c^{d^\ldots}}}\equiv r\cdot\gcd(a,m)\cdot\left(\frac{1}{\gcd(a,m)}\mod {m_1}\right)\pmod {m}$$

---

You can find more information on the Chinese Remainder Theorem (abbreviated as CRT) here and anywhere else, just google it.

Here are two ways of solving a system of $2$ linear congruences that have coprime moduli.

The first one uses the Bezout's Lemma and the Extended Euclidean Algorithm.

They are similar in the way that the $1$st one finds modular multiplicative inverses with the help of the Extended Euclidean Algorithm. We have $\frac{1}{n}\equiv y\pmod m$ and $\frac{1}{m}\equiv x\pmod n$.

$$\begin{cases}a\equiv r_m\pmod m\\a\equiv r_n\pmod n\\\gcd(m,n)=1\\mx+ny=1\\a,r_m,r_n,x,y,m,n\in\mathbb Z\end{cases}\implies r_n(mx)+r_m(ny)\equiv \text{answer}\pmod {mn}$$

$$\begin{cases}a\equiv r_m\pmod m, \frac{1}{n}\equiv n''\pmod {m}\\ a\equiv r_n\pmod n, \frac{1}{m}\equiv m''\pmod n\\\gcd(m,n)=1\\a,r_m,r_n,n'',m'',m,n\in\mathbb Z\end{cases}\implies r_mnn''+r_nmm''\equiv \text{answer}\pmod {mn}$$