2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What about the order of power calculation?? $\endgroup$ – Hamid Reza Ebrahimi Jan 29 '17 at 3:47
  • $\begingroup$ @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}}}$. $\endgroup$ – S.C.B. Jan 29 '17 at 3:51
  • $\begingroup$ Start from the exponents downwards: $(12)^{34^{56^{78}}} = (12)^{34^{(2.28\cdot 10^{136})}} = ...$ etc $\endgroup$ – Arnold Frenzy Jan 29 '17 at 3:52
  • $\begingroup$ Isn't CRT helpful further, by this 3 must be remainer $\endgroup$ – Subhash Chand Bhoria Jan 29 '17 at 3:54
  • $\begingroup$ @SubhashChandBhoria What do you mean? $\endgroup$ – S.C.B. Jan 29 '17 at 3:55
3
$\begingroup$

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

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

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$

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.