# Last digit of sequence of numbers

We define the sequence of natural numbers $$a_1 = 3 \quad \text{and} \quad a_{n+1}=a_n^{a_n}, \quad \text{ for n \geq 1}.$$

I want to show that the last digit of the numbers of the sequence $a_n$ alternates between the numbers $3$ and $7$. Specifically, if we symbolize with $b_n$ the last digit of $a_n$, I want to show that $$b_n = \begin{cases} 3, & \text{if n is odd}, \\ 7, & \text{if n is even}. \end{cases}$$

There is a hint to prove that for each $n \in \mathbb{N}$, if $a_n \equiv 3 \pmod{5}$ then $a_{n+1} \equiv 2 \pmod{5}$ and if $a_n \equiv 2 \pmod{5}$ then $a_{n+1} \equiv 3 \pmod{5}$.

First of all, if we take $a_n \equiv 3 \pmod{5}$, then $a_{n+1}=3^3\pmod{5} \equiv 2 \pmod{5}$.

If $a_n \equiv 2 \pmod{5}$, then $a_{n+1}=2^2 \pmod{5}=4$. Or am I doing something wrong?

And also how does it follow, if we have shown the hint, that $b_n$ is $3$ when $n$ is odd, and $7$ if $n$ is even?

• You can't just do modulo the power like that. Use Fermat's little theorem Aug 27, 2018 at 12:05
• How else do we calculate it? @Rumpelstiltskin Aug 27, 2018 at 12:07
• If $a_n \equiv 2\textrm{ (mod 5)}$ you have $a_n = 5k+2$ for any whole number $k$. Now I would try to calculate $(5k+2)^{5k+2}$ by using the binomial formula. Keep in mind that you calculate mod 5, so multiples of 5 vanish. This should make it easier. Aug 27, 2018 at 12:17

It follows directly from the hint:

The last digit of $a_n$ is the residue class of $a_n$ mod 10.

Now if you have $a_n \equiv 3 \textrm{ (mod 5)}$ it follows $a_n \equiv 3 \textrm{ (mod 10)}$ or $a_n \equiv 8 \textrm{ (mod 10)}$. But $a_n \equiv 8 \textrm{ (mod 10)}$ would mean that $a_n$ is even, so $2$ comes in the prime factorization of $a_n$, but the only prime dividing $a_n$ is 3, so this is not possible.

In the same way, from $a_n\equiv 2\textrm{ (mod 5)}$ you get $a_n \equiv 7\textrm{ (mod 10)}$.

• I have a question. We have that $a_1=3$. The last digit of $a_2$ is $3^3 \pmod{10}=7$. The last digit of $a_3$ is $7^7 \pmod{10}=3$. The last digit of $a_4$ is $3^3 \pmod{10}=7$, and so on. Why doesn't this suffice? Aug 27, 2018 at 18:23
• I guess you hang on the mistake that Stefan4024 explains quite detailed. Let me try to express it in a slightly different way: Let $a \textrm{ mod } b$ denote the residue class of $a$ modulo $b$, for example $23\textrm{ mod }10=3$. Then what you probably want to argue is $a_{n+1}\textrm{ mod 10 } = (a_n \textrm{ mod }10)^{a_n \textrm{ mod }10}\textrm{ mod }10$. But this is wrong.In your original question you struggled on proving the hint since you did this mistake (with mod 5 instead of mod 10). PS: Please upvote useful answers and mark your favourite answer. Aug 27, 2018 at 19:36
• Ok, but how do we get from the result you wrote at your post the desired conclusion? @S.M.Roch Sep 14, 2018 at 22:31

The mistake you are making is that if $a_n \equiv 2 \pmod 5$ it's not true that $a_n^{a_n} \equiv 2^2 \pmod 5$. The reason behind this is that the exponents aren't repeating in blocks of $5$, but instead in blocks of $\phi(5) = 4$, in your case. Indeed by Fermat's Little Theorem we have that $a_n^4 \equiv 1 \pmod 5$. Thus you need to find $a_n \pmod 4$ first.

This isn't hard to do, as $a_1 = 3$. Thus whenever it's raised to an odd power we get that $a_n \equiv -1 \pmod 4$. Hence we have:

$$a_n \equiv a_{n-1}^{a_{n-1}} \equiv a_{n-1}^{-1} \pmod 5$$

Now use the fact that $2$ is the modular inverse of $3$ modulo $5$ to conclude that:

$$a_n \equiv \begin{cases} 3 \pmod 5, & \text{if n is odd} \\ 2 \pmod 5, & \text{if n is even} \end{cases}$$

Finally note that $a_n \equiv 1 \pmod 2$ and use Chinese remainder Theorem to conclude that:

$$a_n \equiv \begin{cases} 3 \pmod{10}, & \text{if n is odd} \\ 7 \pmod{10}, & \text{if n is even} \end{cases}$$

• Could you explain to me how we use the fact that $a_n \equiv -1 \pmod{4}$ if we have an odd power? Sep 14, 2018 at 22:33
• @Evinda For example we have that $a_2 \equiv a_1^{a_1} \equiv (-1)^{a_1} \pmod 4$. Now as $a_1$ is odd we get that $a_2 \equiv -1 \pmod 4$. We can inductively this holds for all $n$. Then as the $a_n^4 \equiv 1 \pmod 5$ we get that: $$a^{n+1} \equiv a_n^{a_n} \equiv a_n^{4k - 1} \equiv a_n^{-1} \pmod 5$$ Sep 15, 2018 at 3:15

First, you should prove that $a_n$ is odd for all $n$ : this follows from the fact that $a_1$ is odd, and if $a_n$ is odd, then $a_{n+1}=a_n^{a_n}$ is an odd number multiplied with itself some number of times, so it is odd.

Let us notice something more. First, $a_1 = 3 \equiv 3 \mod 4$. Next, if $a_n \equiv 3 \mod 4$, then $a_{n+1} \equiv 3^{a_n} \equiv 3^1 \mod 4$ (as $3^2 = 9 \equiv 1 \mod 4$, we may take remainder when $a_n$ is divided by $2$, and this is $1$ since $a_n$ is odd).

Thus, $a_n \equiv 3 \mod 4$ for all $n$.

To the main part.

If $a_n \equiv 3 \mod 5$, then $a_{n+1} = a_n^{a_n} \equiv 3^{a_n} \mod 5$ is all you can say using the fact that $a_n \equiv 3 \mod 5$. But note that $3^{4} \equiv 1 \mod 5$, so you can now say that $a_{n+1} \equiv 3^{(a_n \mod 4)} \mod 5$.

But the point is, that $a_n$ is odd, so $a_n \mod 4$ is either $1$ or $3$. Consequently, $a_{n+1} \equiv 3^1 = 3 \mod 5$ or $a_{n+1} \equiv 3^3 = 27 \mod 5$ must happen. We appear somewhat stuck here. Let me relieve you : we are doing fine.

With the above observation combined with the second part, we have $a_{n+1} \equiv 27 = 2 \mod 5$.

Now, if $a_n \equiv 2 \mod 5$, then $a_{n+1} \equiv 2^{a_n} \mod 5$, and again we equate this to $2^{a_n \mod 4} \mod 5 = 2^3 =8 \equiv 3 \mod 5$.

Thus, $a_{n+1} \equiv 3 \mod 5$.

So the remainders of $a_n$ and $a_{n+1}$ alternate modulo $5$. Since all $a_n$ are odd, this forces their last digits to alternate, and from knowing that the last digit of $a_1$ is $3$, the sequence of last digits must go $373737373...$

• I haven't understood how we get that $a_{n+1}=3^{(a_n \bmod{4})} \bmod{5}$... Could you explain it further to me? Sep 14, 2018 at 22:35
• Yes. See, $a_n \mod 4$ is the unique integer $0 \leq r < 3$ such that $a_n \equiv r \mod 4$. Therefore, $a_n = r + 4k$ for some integer $k$. Consequently, $3^{a_n} = 3^{4k}3^r$. Since $3^{4k} =(9)^{2k}$ leaves a remainder of $1$ modulo $4$, we conclude that $3^{a_n} \equiv 3^r \mod 4$, and now remembering what $r$ was gives the result. Sep 15, 2018 at 0:54