Exponential A.P

Name the expression $A$ . We must calculate $A$ mod 1000, and do that by considering both $A$ mod 8 and $A$ mod 125. First of all, $A = 9^B \equiv 1^B \equiv 1\ \text{mod}\ 8.$ For the mod 125, we need to know the exponent $B$ modulo $\phi(125) = 100 = 4\times 25$ . Writing $B = 8^C,$ we see immediately that $B = 8^C \equiv 0^C \equiv 0\ \text{mod}\ 4.$ It takes more effort to find $8^C$ modulo 25. This requires that we find $C$ modulo $\phi(25) = 20 = 4\times 5.$

Start by writing $C = 7^D$ . Since $D$ , a power of 6, will be even, we have $C = 7^D \equiv (-1)^D \equiv 1\ \text{mod}\ 4.$ Also, considering the fact that $D = 6^E$ will be a multiple of $4 = \phi(5)$ , we have $C \equiv 2^D \equiv 2^0 \equiv 1\ \text{mod}\ 5.$ Combining what we have about $C$ we conclude $C \equiv 1\ \text{mod}\ 20;$ $B = 8^C \equiv 8^1\equiv 8\ \text{mod}\ 25.$ Combine this with $B \equiv 0$ mod 4, and we have $B \equiv 8\ \text{mod}\ 100;$ $A = 9^B \equiv 9^8 \equiv 81^4 \equiv 61^2 \equiv 221\ \text{mod}\ 125.$ Finally, combined with $A \equiv 1$ mod 8, this results in $A \equiv \boxed{721}\ \text{mod}\ 1000.$

My approach is similar to Arjen's. I will use Arjen's time-saving notation $A=9^B=9^{8^C}=9^{8^{7^D}}$ . Let's consider the Carmichael Lambda throughout, with $\lambda(1000)=100,\lambda(25)=20$ and $\lambda(20)=4$ .

Now $D\equiv 0\pmod{4}$ so $C=7^D\equiv 7^0= 1\pmod{20}$ and $B=8^C\equiv 8^1=8\pmod{25}$ . It follows that $B\equiv 8 \pmod{100}$ as well so that $A=9^B\equiv 9^8=(-1+10)^8\equiv 1-8*10+{8\choose 2}100\equiv \boxed{721} \pmod{1000}$

The question is finding $\large{ \color{#3D99F6}9^{\color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}}$ modulo $1000$ . By Euler's Theorem, The question can be changed to be

$\large{ \color{#3D99F6}9^{\color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}}\equiv\begin{cases}1\pmod{8}\\ \large \color{#3D99F6}9^{\left(\color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}\bmod~{\phi(1000)}\right)}\pmod{125}\end{cases}$

We need to find $\large{ \color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}$ modulo $\phi(1000)=1000\times{\left(1-\frac{1}{2}\right)}\times{\left(1-\frac{4}{5}\right)}=400$

Now, we find the residu of $\large{ \color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}$ modulo $16$ and $25$ . Note that $8^{2}\equiv0\pmod{16}$ , then since $\large{ \color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}=8^2\times{8^n}$ , so $\large{ \color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}\equiv0\pmod{16}$ . Now, by using Euler's Theorem with $\phi(25)=20$ we evaluate

$\large{\color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}\equiv\begin{cases}0\pmod{16}\\ \color{#20A900}8^{\left(\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}\bmod~{20}\right)}\pmod{25}\end{cases}$

We need to find $\large\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}$ modulo $20$ , then we must find $\large\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}$ modulo $\phi(20)=8$ . Note that $6^{3}\equiv0\pmod{8}$ . Since $\large\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}=6^{3}\times{6^{m}}$ , so $\large\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}\equiv0\pmod{8}$ . Now, we have $\large\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}\equiv7^{0}\pmod{20}$ .

Thus,

$\large{ \color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}\equiv\begin{cases}0\pmod{16}\\ 8\pmod{25}\end{cases}$

Using Chinese Rimainder Theorem we get $\large{ \color{#20A900}8^{\color{#D61F06}7^{\color{#624F41}6^{\color{#302B94}5^{\color{magenta}4^{\color{grey}3^{\color{#BA33D6}2^\color{#E81990}1}}}}}}}\equiv208\pmod{400}$ . Now, using this value, our first congruence system becomes

$\large{ \color{#3D99F6}9^{208}}\equiv\begin{cases}1\pmod{8}\\ 96\pmod{125}\end{cases}$

Finally, again using Chinese Rimainder Theorem, we get $\large{ \color{#3D99F6}9^{208}}\equiv721\pmod{1000}$

Hence, the answer is $\large{\boxed{721}}$

Brute Force.

• We need to find $x=9^a \mod{1000}$ .

• Find the cycle of 9 modulo 1000. It's

  [9, 81, 729, 561, 49, 441, 969, 721, 489, 401, 609, 481, 329, 961, 649, 841, 569, 121, 89, 801, 209, 881, 929, 361, 249, 241, 169, 521, 689, 201, 809, 281, 529, 761, 849, 641, 769, 921, 289, 601, 409, 681, 129, 161, 449, 41, 369, 321, 889, 1]

Which is of length $\boxed{50}$ .

• So, now find $a=8^b \mod{50}$ .

• Cycle of 8 modulo 50. It's

  [8, 14, 12, 46, 18, 44, 2, 16, 28, 24, 42, 36, 38, 4, 32, 6, 48, 34, 22, 26]

Which is of length $\boxed{20}$ .

• Now find $b=7^c \mod{20}$ .

• Cycle of 7 modulo 20. It's

  [7, 9, 3, 1]

Which is of length $\boxed{4}$ .

• $c=6^{5^{\cdots}}=0 \mod{4}$ .

• $\therefore b=1 \mod{20}$

• $\therefore a=8 \mod{50}$

• $\therefore \boxed{x=721 \mod{1000}}$

we know that $x^n\equiv x^{n\pmod{\phi(m)}} \pmod {m}$ . where $\phi(k)$ is eulerss toitent function. using this continuously on all the exponents, . we start computing from thr top, but wait! we see that $6^{5^{\cdots}}\equiv 0 \pmod {64}$ . so we can just ut it as 0 to get $7^0$ . we see that it becomes one making the exponent: $9^{8^1}\equiv (9^4)^2\equiv 561^2\equiv \boxed{721}\pmod{1000}$