# Calculate remainder of $12^{34^{56^{78}}}$ when divided by $90$

Calculate remainder of $12^{34^{56^{78}}}$ when divided by $90$

First of all,I'm not sure about the order of calculation of powers!
Secondly I don't know the rules of finding remainder moulus 90

$90=2 \times 3^2 \times 5$, so let us divide the cases. First note $$12^{34^{56^{78}}} \equiv 0 \pmod {2}$$$$12^{34^{56^{78}}}=4^{34^{56^{78}}} \times 3^{34^{56^{78}}} \equiv 0 \pmod {3^2}$$ Also, since $56^{78}>2$, $34^{56^{78}} \equiv 0 \pmod {4}$. Let $34^{56^{78}} =4k$ where $k$ is a natural. So $$12^{34^{56^{78}}}=12^{4k}=(12^{4})^k \equiv 1^k \equiv 1 \pmod {5}$$ From Fermat's Little Theorem. Now use CRT. So we have that $$12^{34^{56^{78}}} \equiv 36 \pmod {90}$$

• What about the order of power calculation?? – Hamid Reza Ebrahimi Jan 29 '17 at 3:47
• @HamidRezaEbrahimi If you see my answer, you can see the order in which he calculate powers. First calculate $56^{78}$. Then calculate $34^{56^{78}}$. Then calculate $12^{34^{56^{78}}}$. – S.C.B. Jan 29 '17 at 3:51
• Start from the exponents downwards: $(12)^{34^{56^{78}}} = (12)^{34^{(2.28\cdot 10^{136})}} = ...$ etc – Arnold Frenzy Jan 29 '17 at 3:52
• Isn't CRT helpful further, by this 3 must be remainer – Subhash Chand Bhoria Jan 29 '17 at 3:54
• @SubhashChandBhoria What do you mean? – S.C.B. Jan 29 '17 at 3:55

Hint $\,\ N>0\,\Rightarrow\,18\mid 12^{4N}\!\Rightarrow 12^{4N}\!\bmod{90} \,=\,18\underbrace{\left(\dfrac{(12^{4})^N}{18}\bmod 5\right)}_{\equiv\ \dfrac{1^N}{3}\ \equiv\ \dfrac{6}3\equiv\ \Large\color{#c00} 2} =\, 18(\color{#c00}2)\$

• We used the mod Distributive Law $\ ca\bmod cn = c(a\bmod n)\ \$ – Bill Dubuque Jan 30 '17 at 3:57
• @Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. – Bill Dubuque Feb 15 '17 at 22:42

As $34^{56^{78}}$ is divisible by $4,$ let us write this as $4(m+1)$

As $(12^n,90)=18$ for $n\ge2$ let us find $12^{4(n+1)-2}\pmod{90/18}$

i.e., $12^{4n+2}\pmod5$

Now as $12\equiv2\pmod5,12^2\equiv2^2\equiv-1$

$12^{4m+2}=(12^2)^{2m+1}\equiv(-1)^{2m+1}\equiv-1\pmod5$

$\implies12^{4(m+1)}\equiv12^2\cdot-1\pmod{12^2\cdot5}\equiv-144\pmod{90}$ as $90|12^2\cdot5$

Finally $-144\equiv36\pmod{90}$ as $12^{4(m+1)}>0$

Working through this slowly:

For the sequence $12^k \bmod 90$, we can see this will quickly settle onto multiples of $18$, since $12$ and $90$ share $2$ and $3$ as prime factors and $2\cdot 3^2$ is the largest factor of $90$ using these prime factors.

So the sequence $12^k \bmod 90$ looks like $\{12, \color{blue}{54}, 18, 36, 72, \color{blue}{54}, \ldots\}$ with a cycle length of $4$, and thus $12^{4i}\equiv 36 \bmod 90$ for $i\ge 1$.

Then for $j>1$, $4 \mid 34^j$ and thus $12^{34^{56^{78}}}\equiv 36 \bmod 90$

My solution is rather routine and makes good use of Euler totient theorem and modulus properties.

\begin{align*}12^{34^{45^{78}}} \pmod{90} &\equiv 6\left[\frac{12^{34^{45^{78}}}}{6} \pmod{15} \right],\qquad\qquad\gcd(12,90)=6\\ &\equiv 18\left[\frac{12^{34^{45^{78}}}}{18} \pmod{5}\right],\qquad\qquad\gcd(12,15)=3\\ &\equiv 18\left[\frac{2^{34^{45^{78}}\pmod 4}}{3} \pmod{5}\right],\qquad\qquad\phi(5)=5-1=4\\ &\equiv 18\left[\frac{2^0}{3} \pmod{5}\right]\\ &\equiv 18\left[\frac{6}{3} \pmod{5}\right]\\ &\equiv 18\left[2\right]\equiv 36 \end{align*}