# Thread: Very tricky and interesting modular question

1. ## Very tricky and interesting modular question

This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!

2. Originally Posted by elemental
This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!
James Bond +1 ?

3. Originally Posted by elemental
This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!
Spoiler:

Preamble: I think there's a more elegant way to write down the same type of reasoning, but this is the first that came to mind.

Combination of Euler's theorem and Chinese remainder theorem.

$\displaystyle 2008^{2007^{2006^{\dots^{1}}}} \equiv 8^{2007^{2006^{\dots^{1}}}} \equiv x\ (\text{mod}\ 1000)$

Solve

$\displaystyle 8^{2007^{2006^{\dots^{1}}}} \equiv a\ (\text{mod}\ 2^3)$

$\displaystyle 8^{2007^{2006^{\dots^{1}}}} \equiv b\ (\text{mod}\ 5^3)$

and then combine with CRT.

Note that $\displaystyle 8^{2007^{2006^{\dots^{1}}}} \equiv 0\ (\text{mod}\ 2^3)$

Solve $\displaystyle 8^{2007^{2006^{\dots^{1}}}} \equiv b\ (\text{mod}\ 5^3)$

$\displaystyle \gcd(8,5^3) = 1$

Use Euler's theorem

$\displaystyle \varphi(5^3)=100$

Reduce to finding $\displaystyle 2007^{2006^{2005^{\dots^{1}}}} \equiv 7^{2006^{2005^{\dots^{1}}}} \equiv c\ (\text{mod}\ 100)$

$\displaystyle \gcd(7,100) = 1$

Use Euler's theorem

$\displaystyle \varphi(100)=40=2^3\cdot5$

$\displaystyle 2006^{2005^{2004^{\dots^{1}}}} \equiv 6^{2005^{2004^{\dots^{1}}}} \equiv d\ (\text{mod}\ 40)$

$\displaystyle \gcd(6,40) = 2$

Solve

$\displaystyle 6^{2005^{2004^{\dots^{1}}}} \equiv e\ (\text{mod}\ 2^3)$

$\displaystyle 6^{2005^{2004^{\dots^{1}}}} \equiv f\ (\text{mod}\ 5)$

Note that $\displaystyle 6^{2005^{2004^{\dots^{1}}}} \equiv 0\ (\text{mod}\ 2^3)$

Note that $\displaystyle 6^{2005^{2004^{\dots^{1}}}} \equiv 1^{2005^{2004^{\dots^{1}}}} \equiv 1\ (\text{mod}\ 5)$

Now work backwards...

CRT: $\displaystyle 2006^{2005^{2004^{\dots^{1}}}} \equiv 16\ (\text{mod}\ 40)$

Euler: $\displaystyle 2007^{2006^{2005^{\dots^{1}}}} \equiv 7^{16} \equiv 1\ (\text{mod}\ 100)$

Euler: $\displaystyle 2008^{2007^{2006^{\dots^{1}}}} \equiv 8^1\ \equiv 8\ (\text{mod}\ 5^3)$

CRT: $\displaystyle 2008^{2007^{2006^{\dots^{1}}}} \equiv 8\ (\text{mod}\ 1000)$

So the answer is 008

Just like Also sprach Zarathustra said!

4. ## Ignore

Originally Posted by elemental
This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!
Assuming you meant $\displaystyle 2008^{2007^{2006^{2005^{2004...^{1}}}}}$, call it $\displaystyle P$ and let $\displaystyle a=2007^{2006^{2005^{2004...^{1}}}}$ and $\displaystyle b=2006^{2005^{2004...^{1}}}$.

I start with the fact that $\displaystyle 2008\equiv 3\equiv -2(mod\ 5)$.

$\displaystyle b=2k$ for some integer $\displaystyle k$, so $\displaystyle a=2007^b=2007^{2k}\equiv 3^{2k}\equiv 9^k\equiv 1(mod\ 4)$.
$\displaystyle a=4t+1$ for some integer $\displaystyle t$, so $\displaystyle (-2)^a=(-2)^{4t+1}=16^t(-2)\equiv-2(mod\ 5)$

Now, $\displaystyle P=2008^a\equiv (-2)^a\equiv(-2)(mod\ 5)$. Also, obviously $\displaystyle P$ is even, hence $\displaystyle P\equiv -2(mod\ 2)$. These two congruences give $\displaystyle P\equiv -2\equiv 8(mod\ 10)$.

The last digit of $\displaystyle 2008^{2007^{2006^{2005^{2004...^{1}}}}}$ is $\displaystyle 8$.

5. Well done guys, 008 is indeed correct.

6. Challenge questions belong in the Challenege Questions subforum (read the rules at that subforum before posting in it).

7. We wish to find out the remainder when $\displaystyle 2006^{2005^{...}}$ is divided by $\displaystyle 40$

Let $\displaystyle x$ be $\displaystyle 2006^{2005^{...}}$

then

$\displaystyle x \equiv 1 \bmod{5}$ and

$\displaystyle x \equiv 0 \bmod{8}$ so

$\displaystyle \boxed{ x \equiv 16 \bmod{40} }$

Then consider $\displaystyle 7^x$ in modulo $\displaystyle 100$

it is $\displaystyle 7^{40k + 16} \equiv 7^{16 }\bmod{100}$

Let $\displaystyle y = 7^{16 }$ we have

$\displaystyle y \equiv (-1)^{16} \equiv 1 \bmod{4}$ and

$\displaystyle y = 7^{16} = (49)^8 \equiv (-1)^8 \equiv 1 \bmod{25}$ so

$\displaystyle y \equiv 1 \bmod{100}$

Then $\displaystyle 8^y$ in modulo $\displaystyle 125$

Since $\displaystyle (8,125) = 1$ we have $\displaystyle 8^{100} \equiv 1$

Therefore , $\displaystyle 8^y = 8^{100k + 1 } \equiv 8 \bmod{125}$

Together with $\displaystyle 8^y \equiv 0 \bmod{8}$ we obtain $\displaystyle 8^y \equiv 8 \bmod{1000}$

Actually , the answer is exactly $\displaystyle 8 \equiv 8^y \equiv (2008)^y \bmod{1000}$