The answer is 36.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

What an unorthodox way to force out an answer. Ingenious!

Brilliant.

Mehul Arora
- 5 years, 4 months ago

This problem seems monstrous at first but is actually very easy to compute! Don't let the powers scare you. First, we prove the following trivial lemma.

**
Lemma:
**
$\forall~x,y\in\Bbb{Z^+}\mid x\geq y\iff a^x\equiv 0\pmod{a^y}~\forall~a\in\Bbb{Z}$

**
Proof:
**
$\forall~x,y\in\Bbb{Z^+}\mid x\geq y\iff \exists~ c\in\Bbb{Z_0^+}\mid a^x=a^{y+c}=a^y\cdot a^c\equiv 0\pmod{a^y}$

Hence, the lemma is proved and established.

Coming back to our problem, we compute the residue of the value in the problem modulo coprime values $2,5,9$ . We use Fermat's Little Theorem for calculating modulo $5$ and use the proved lemma in both modulo $5$ and $9$ calculations. Take the value as $X$ . Then,

$X\equiv 0\pmod{2}~~\textrm{(since 12 is even, the whole expression must be even)}$

$\large X\equiv 12^{\left(34^{56^{78}}~\bmod~4\right)}\equiv 12^{\left(2^{56^{78}}~\bmod~2^2\right)}\equiv 12^0\equiv 1\pmod5$

$12\equiv 3\pmod9\implies \large X\equiv 3^{34^{56^{78}}}\pmod{9=3^2}\implies X\equiv 0\pmod9$

These results can be summarized as follows:

$X\equiv\begin{cases}0\pmod2\\ 1\pmod5\\ 0\pmod9\end{cases}$

Using Chinese Remainder Theorem, one can easily get that $X\equiv 36\pmod{90}$ .

$\Large\therefore\quad X=12^{34^{56^{78}}}\equiv 36\pmod{90}$

**
Clarifications:
**

- The vertical bar symbol, $~"~\mid~"~$ used here denotes "such that".
- $\exists$ and $\forall$ are quantifier operators denoting "there exists" and "for all" respectively.
- $\iff$ represents the "if and only if" condition.

37 Helpful
1 Interesting
3 Brilliant
1 Confused

Great use of Chinese Remainder Theorem (CRT).

**
Bonus question
**
: do you need CRT to solve this congruence:
$\large 2^{3^{4^{.^{.^{.^{9}}}}}} \pmod{10}$
?

**
[Response to Challenge Master Note]
**

Well, no, we don't really need CRT for the bonus question and also for the solution to the original problem. Here's a non-CRT solution for the bonus question (we use Fermat's Little Theorem for the modulo $5$ calculation):

$\large 2^{3^{4^{.^{.^{.^{9}}}}}}\equiv\begin{cases}0\pmod2\\ 2^{\left(3^{4^{.^{.^{.^{9}}}}}~\bmod~4\right)}\equiv 2^{\left((-1)^{4^{.^{.^{.^{9}}}}}~\bmod~4\right)}\pmod5\end{cases}$

Since $4$ is even, any arbitrary positive exponentiation is also even and we know that $(-1)^{\textrm{even value}}=1$ , hence, our above congruence system becomes,

$\large 2^{3^{4^{.^{.^{.^{9}}}}}}\equiv\begin{cases}0\pmod2\\ 2^{1~\bmod~4}\pmod5\end{cases}\implies \large 2^{3^{4^{.^{.^{.^{9}}}}}}\equiv\begin{cases}0\pmod2\\ 2\pmod5\end{cases}$

$2\mod 5$ implies that the answer is either $2$ or $7$ but we also have $~0\mod 2$ which rules out $7$ as a possible answer since it's odd. Hence, the answer is undoubtedly $2$ , i.e.,

$\Large\therefore\quad 2^{3^{4^{.^{.^{.^{9}}}}}}\equiv 2\pmod{10}$

**
Alternate ending of my solution to the original problem:
**

For the original solution I posted to this problem, let me demonstrate a non-CRT approach to get the final result:

$X\equiv\begin{cases}0\pmod2\\ 0\pmod9\\ 1\pmod5\end{cases}\implies X\equiv\begin{cases}0\pmod{9\times 2=18}\\ 1\pmod5\end{cases}$

$0\mod 18$ implies that the answer must be one of the following values: $0,18,36,54,72$ . But we also have $~1\mod 5$ . Among the listed values, only $36$ satisfies the modulo $5$ result, i.e., it's the only value in the list which is congruent to $1$ modulo $5$ . Hence, our answer is $36$ which is the same as we got in the original solution using CRT.

P.s - It can be seen that CRT is really not needed for both the problems. I use CRT since it's a no-brainer. :P

Prasun Biswas
- 6 years, 1 month ago

**
Challenge taking student note :
**
Nicely done and presented.You need sleep.

Nihar Mahajan
- 6 years, 1 month ago

Log in to reply

What makes you a challenge student ? I have recently started seeing yellow boxes with " Challenge Master Note : ", even in my solutions, and now seeing that you are a "Challenge Student". What are these titles ? Please do explain, and thanks in advance :).

Venkata Karthik Bandaru
- 6 years, 1 month ago

Log in to reply

Well , that's my way to praise or comment others . Nothing so special in it. Actually , all students who learn something or the other thing , are considered as challenge students in my opinion.Thanks!

Nihar Mahajan
- 6 years, 1 month ago

at what level of math do these type of problems become routine? I "learned" math up to and including non multivariable calculus and while i've heard of fermat, we never learned his little theorem in my math classes. I realize that at heart these are essentially pre-algebra with their lack of variables (no x s, that i've seen thus far), but my pre-algebra teacher never taught the theorems mentioned and our tests were infinitely-1 easier than these questions. In what college or even grad school level classes are these theorem essential to mastering the class? Thanks in advance for any response other than sarcasm.

Brett Ozga
- 4 years, 10 months ago

Log in to reply

These are number theory problems (as can be seen from the heading :P). These types of problems are typically familiar to those studying number theory (at college, say) or people who give exams like the Mathematical Olympiad.

The basic ideas behind number theory, the ones at play here, are truly simple. But a pre-algebra student would have a lot of difficulties grasping the subtle ideas behind many of the proofs. (Take a look at the CRT proof used in Number Theory books. In my opinion, the one on the brilliant.com website is much easier to understand.)

As for the difficulty of these questions, I wouldn't say that these are much more difficult than those that one is used to. They are just of a different type. With a little bit of practice, it becomes much easier.

The reason most students never come across these number theoretic in traditional math classes is that traditional math classes are more geared towards teaching the more "practical" aspect of mathematics. There are many uses of differentiation and integration (for example, converting a function of displacement vs time to velocity vs time in physics) and many more of Differential Equations (modeling the population of a city, modeling heat transfer between an object and its surroundings (Newton's Law of Cooling, Heat Equation), and modeling the radiation output of a radioactive material, just to name a few).

The different types of calculus (single variable and multivariable) find many such uses in Physics, Chemistry, and Engineering. Relatively speaking, there is no such use in knowing that $a^{p-1} \equiv 1 \pmod p$ or knowing that $(p-1)! \equiv -1 \pmod p$ . (Nowadays, one can find some applications of the former in cryptography, but that's about it).

Tirthankar Mazumder
- 2 years, 2 months ago

11 Helpful
0 Interesting
0 Brilliant
0 Confused

$90=2\cdot 3^2\cdot 5$ . Clearly $12^{34^{56^{78}}}=2\cdot 3^2\cdot k=18k$ .

By FLT, mod $5$ : $\ 12^{34^{56^{78}}}\equiv 12^{34^{56^{78}}\pmod{4}}\equiv 12^{0}$

\equiv 1\equiv 6\equiv 18k\equiv 3k\stackrel{:3}\iff k\equiv 2\,\Rightarrow\, k=5c+2 .

$12^{34^{56^{78}}}=18(5c+2)=90c+36$ .

As for Challenge Master: Find $2^{3^{4^{.^{.^{.^{9}}}}}}\bmod{10}$ .

$2^1\equiv 2,\ 2^2\equiv 4,\ 2^3\equiv 8,\ 2^4\equiv 6,\ 2^5\equiv 2,\ldots$ mod $10$ , and $3^{4^{\cdots}}\equiv (-1)^{4^{\cdots}}\equiv 1\pmod{4}$ , so $2^{3^{4^{.^{.^{.^{9}}}}}}\equiv 2^1\equiv 2\pmod{10}$ .

2 Helpful
1 Interesting
0 Brilliant
0 Confused

Shouldn't 12^34^56^78=12^[34^(56^78)]?

Xianghuai Wang
- 4 months, 3 weeks ago

Working out the multiplicative cycle generated by $12\textnormal{ (mod }90)$ , we see that if the exponent is:

- $0\textnormal{ (mod }4)$ we get $36$
- $1\textnormal{ (mod }4)$ we get $72$
- $2\textnormal{ (mod }4)$ we get $54$
- $0\textnormal{ (mod }4)$ we get $18$

Similarly for the multiplicative cycle generated by $36\textnormal{ (mod }4)$ we get 0 for any exponent $\geq 2$ , so then the answer must be $\color{#20A900}{\boxed{36}}$ .

0 Helpful
0 Interesting
0 Brilliant
0 Confused

For simplicity, let $x:=\green{34}^{\blue{56}^{78}}$ . Notice that $x=4k\geq 4$ , so we have $\gcd(12^x,\:90)=18$ and cannot use Euler's Theorem directly! Instead, we factor out the common divisor $18$ , and use Euler's Theorem $(*)$ for the remaining inner modulus of $5$ : $\begin{aligned} 12^x &\equiv 18\left( \frac{12^x}{18} \mod 5 \right) \equiv 18\left( 12^{x-2}\cdot 8\mod 5 \right)\qquad \left|x=4k\qquad \left|12^4\equiv 1\mod 5\quad (*)\right.\right.\\[1.25em] &\equiv 18\left( 12^{4k-4}\cdot 12^2\cdot 8\mod 5 \right)\underset{(*)}{\equiv} 18\left( 1^{k-1}\cdot2^2\cdot 3\mod 5 \right) \equiv 18\cdot 2\equiv \boxed{36}\mod 90 \end{aligned}$

**
Rem.:
**
Recall the following useful property to get rid of common divisors of base and modulus:
$\begin{aligned}
a&\in\mathbb{Z}, &n&\in\mathbb{N},&\gcd(a,\:n)&=g&&&\Rightarrow&&&& a\equiv g\cdot\left(\frac{a}{g}\mod \frac{n}{g}\right)\mod n
\end{aligned}$

0 Helpful
0 Interesting
0 Brilliant
0 Confused

We can figure out 2 key things about 12^(34^(56^(78))):

- Since 2m^(4n) = a number ending in 6, so must 12^(34^(56^(78))), since 34^(56^(78)) = 2a^(2b) = 4c
- Since 3m^n (when n>1) = 9x, so must 12^(34^(56^(78)))

Thinking of 12^(34^(56^(78))) = 9m and 90x = 9n (90x being the largest multiple of 90 less than 12^(34^(56^(78)))), you can then think of the remainder as 9(m-n). Additionally (more like subtractionally, lol), the remainder is (number ending in 6) - (number ending in 0), so the remainder’s last digit is 6. Finally, a remainder is always less than the denominator: in this case, 90. Thus we need a multiple of 9 ending with 6 that is less than 90: 36

0 Helpful
0 Interesting
0 Brilliant
0 Confused

what I did was something very simple actually. 90 = 10 * 9 so now X = 12^34^56^78 mod 90 can be broken down to ((12^34^56^78) mod 10) * 9 * 9 + ((12^34^56^78 * 10 * 1)mod 9) mod 90 (using Chinese remainder theorem) k = (some other terms, but we don't care since this whole thing blows up) = 10*1

That is equal to (2^(4m) mod 10) * 9 * 9 +( (3^(34^56^78) mod 9) * k) mod 90 since 3^(34^56^78) mod 9 = 0 now it is easy to see that 2^(4m) mod 10 = 6 X = (6 * 9 * 9 mod 90) Therefore, X = (6 * 9 * 9) mod 90 = 486 mod 90 = 36 :)

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

Multiply all the exponents to get 148512 and divide it by 90. This gives a congruence of 12.

The problem becomes 12^12 Mod 90

This becomes (12^2)^6

144 Mod 90

144 is congruent to 56. 56^ 6 is congruent to 36

This becomes (36^2)^3 Mod 90

Answer is 36

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

My method of solving this is a bit intuitive... The units digit of the remainder can be determined using the power cycle of 2 since the divisor here is 90... clearly the exponent 34^56^78 is divisible by 4 and as 2^(4K) always ends with 6, the above number also would end in 6... also, barring 12^1, every successive power of 12 is a multiple of 9 (as 12^2 = 144 is a multiple of 9)... So, the remainder also has to be a multiple of 9... So, basically, two conditions need to be satisfied here, the remainder needs to end in 6 and be divisible by 9 and of course, be less than 90... the only number satisfying all this is 36... hence, the answer...