# remainder when $a_{1000}$ is divided by $1000$

If $$a_{1}=7,a_{2}=7^7,a_{3}=7^{7^{7}}.$$ Then the remainder when

$$a_{1000}$$ is divided by $$1000$$

what i try

$$a_{1}=7=1\mod(1000)$$ and

$$a_{2}=7^7=1^7\mod(1000)=1\mod(1000)$$

from using modulo theorem

$$a_{3}=7^{7^{7}}=1^7\mod(1000)=1\mod(7)$$

can we say that $$a_{1000}= 1\mod(1000)$$

Help me to solve it please

• Are you implying that $7 \equiv 1$ Mod $1000$? That's not right.
– user284001
Feb 6, 2020 at 13:53
• $7\not \equiv 1 \pmod {1000}$. More importantly, I would read the recursion as saying that $a_n=7^{a_{n-1}}$.
– lulu
Feb 6, 2020 at 13:53
• Recalculate a few of the terms, and you'll see what happens. You will stumble upon a special number, $343$. Feb 6, 2020 at 13:57
• I realise I wasn't being helpful in my first comment so: Can you find the value of $\varphi(1000)$?
– user284001
Feb 6, 2020 at 14:01

The idea of this answer is the same as that of lab bhattacharjee's answer. I'm going to explain the steps in detail.

To find $$a_{1000}=7^{a_{999}}\pmod{1000}$$, the following two steps should help :

• The first step is to find the smallest positive integer $$b$$ such that $$7^b\equiv 1\pmod{1000}$$.

• The second step is to find $$a_{999}\pmod{b}$$.

This is because if we know that $$a_{999}$$ is of the form $$mb+c\ (c\lt b)$$ from the second step, then we can get$$a_{1000}=7^{a_{999}}=7^{mb+c}=(7^b)^m\cdot 7^c\equiv 1^m\cdot 7^c\equiv 7^c\pmod{1000}$$

The fist step is to find the smallest positive integer $$b$$ such that $$7^b\equiv 1\pmod{1000}$$.

Let us observe the pattern :

$$7^1=7,\quad 7^2=49,\quad 7^3=343,\quad 7^4=240\color{red}1$$ This means that the rightmost digit of $$7^i\ (i=1,2,\cdots)$$ is $$7,9,3,1,7,9,3,1,7,9,3,1,\cdots$$ So, we see that $$b$$ is a multiple of $$4$$. So, to find $$b$$, we only need to consider $$7^{4k}\pmod{1000}$$ where $$k\ge 2\in\mathbb Z$$.

$$7^{4k}=(7^4)^k=(2400+1)^{k}$$ $$\stackrel{\text{binomial theorem}}=1+2400\binom k1+\underbrace{2400^2\binom k2+\cdots +2400^k\binom kk}_{\text{each term is divisible by 1000}}$$ $$\equiv 1+2400k\equiv 1+200k\times 12\pmod{1000}$$ So, we see that the smallest positive $$k$$ such that $$7^{4k}\equiv 1\pmod{1000}$$ is $$5$$.

Therefore, it follows that $$b=4\times 5=20$$.

The second step is to find $$a_{999}\pmod{20}$$.

Since $$a_{998}=7^{\text{odd number}}\equiv (-1)^{\text{odd number}}\equiv -1\equiv 3\pmod 4$$, there exists an integer $$n$$ such that $$a_{998}=4n+3$$.

Now, we get $$a_{999}=7^{a_{998}}=7^{4n+3}=7^3\cdot (7^2)^{2n}=7^3\cdot (50-1)^{2n}$$ $$\stackrel{\text{binomial theorem}}=7^3\bigg(1-\underbrace{\binom{2n}{1}50^1+\binom{2n}{2}50^2-\cdots +\binom{2n}{2n}50^{2n}}_{\text{each term is divisible by 20}}\bigg)$$ $$\equiv 7^3\cdot 1\equiv 343\equiv 3\pmod{20}$$

From the second step, we see that there exists an integer $$m$$ such that $$a_{999}=20m+3$$.

Hence, we finally get $$a_{1000}=7^{a_{999}}=7^{20m+3}=(7^{20})^m\cdot 7^3\equiv 1^m\cdot 7^3\equiv \color{red}{343}\pmod{1000}$$

$$a_1=7\equiv\color{red}7\bmod 1000$$.

$$a_2=7^7=823543\equiv543\bmod 1000$$.

$$7^4=2401\equiv401\bmod1000,$$ so $$7^{20}=(7^4)^5\equiv401^5=(400+1)^5\equiv1\bmod1000$$.

Since $$a_2\equiv543\bmod1000,$$ $$a_2\equiv3\bmod20$$. Therefore, $$a_3=7^{a_2}\equiv7^3=343\bmod1000$$.

Can you take it from here?

$$7^4=(50-1)^2=2401$$

$$7^{4n}=(1+2400)^n\equiv1+2400n\pmod{1000}$$

So, $$n$$ must be divisible by $$5$$ to make residue $$\equiv1$$

$$\implies$$ord$$_{1000}7=20$$

We need $$a_{999}\pmod{20}$$

Again, $$a_r,r\ge2$$ are of the form $$7^{4n+3}$$

$$7^{4n+3}=7^3(50-1)^{2n}\equiv3(1-50)^{2n}\equiv3(1-\binom{2n}150)\pmod{20}\equiv3$$

So for $$r\ge2,$$ $$a_{r+1}\equiv7^{3\pmod{20}}\pmod{1000}\equiv7^3$$

This can be solved by induction. We want to show that if $$a_n \mod 1000 \equiv 343 \Rightarrow a_{n+1} \mod 1000 \equiv 343$$

Notice that if $$n\ge 1$$ then $$a_{n+1}=7^{a_n}$$ $$\left( \text{then obviously } a_{n+1}\mod 1000\equiv 7^{a_n} \right)$$. Also notice that powers of 7 modulo 1000 have a cycle of 20 numbers.

$$7^{20y+1}\mod 1000 \equiv 7$$

$$7^{20y+2}\mod 1000 \equiv 49$$

$$7^{20y+3}\mod 1000 \equiv 343$$

$$7^{20y+4}\mod 1000 \equiv 401$$

$$7^{20y+5}\mod 1000 \equiv 807$$

$$7^{20y+6}\mod 1000 \equiv 649$$

$$7^{20y+7}\mod 1000 \equiv 543$$

$$7^{20y+8}\mod 1000 \equiv 801$$

$$7^{20y+9}\mod 1000 \equiv 607$$

$$7^{20y+10}\mod 1000 \equiv 249$$

$$7^{20y+11}\mod 1000 \equiv 743$$

$$7^{20y+12}\mod 1000 \equiv 201$$

$$7^{20y+13}\mod 1000 \equiv 407$$

$$7^{20y+14}\mod 1000 \equiv 849$$

$$7^{20y+15}\mod 1000 \equiv 943$$

$$7^{20y+16}\mod 1000 \equiv 601$$

$$7^{20y+17}\mod 1000 \equiv 207$$

$$7^{20y+18}\mod 1000 \equiv 449$$

$$7^{20y+19}\mod 1000 \equiv 143$$

$$7^{20y}\mod 1000 \equiv 1$$

Where $$y \in \Bbb{Z}$$

So knowing the remainder of $$a_n$$ mod 20 is sufficient to determine the remainder of $$a_{n+1}$$ mod 1000. An alternative way of stating $$a_{n} \mod 1000 \equiv 343$$ is $$\exists x\in\Bbb{Z}\space|\space1000x+343=a_n$$.

$$20(50x+17)+3=a_n\Rightarrow$$ $$a_n \mod 20 \equiv 3$$

This means that $$a_{n+1} \mod 1000 \equiv 343$$.

So if $$a_n \mod 1000 \equiv 343$$ then any $$a_k \mod 1000 \equiv 343$$ where $$k\ge n$$.

$$a_2=7^7=823543=20(41177)+3$$

$$a_2 \mod 20 \equiv 3\Rightarrow$$ $$a_3 \mod 1000 \equiv 343$$

Therefore all $$a_k \mod 1000 \equiv 343$$ where $$k\ge 3$$. This includes $$a_{1000}$$.