# Very tricky and interesting modular question

• Jul 9th 2010, 12:29 PM
elemental
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!
• Jul 9th 2010, 12:57 PM
Also sprach Zarathustra
Quote:

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 ?
• Jul 9th 2010, 02:07 PM
undefined
Quote:

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

Just like Also sprach Zarathustra said!

• Jul 9th 2010, 02:13 PM
melese
Ignore
Quote:

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$.
• Jul 9th 2010, 05:06 PM
elemental
Well done guys, 008 is indeed correct.
• Jul 9th 2010, 07:03 PM
mr fantastic
Challenge questions belong in the Challenege Questions subforum (read the rules at that subforum before posting in it).
• Jul 9th 2010, 07:41 PM
simplependulum
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}$