Problem of the week #70 - July 29th, 2013

[Jameson]

Without using a calculator and explaining your reasoning, find the last digit of \(\displaystyle 7^{7^7}\).
--------------------
Remember to read the POTW submission guidelines to find out how to submit your answers!

 

[Jameson]

Congratulations to the following members for their correct solutions:

1) MarkFL
2) anemone
3) kaliprasad
4) soroban
5) Opalg
6) Deveno

Solution (from MarkFL):

Spoiler

We are asked to find the last digit of \(\displaystyle 7^{7^7}\).

We may use the binomial theorem to state:

\(\displaystyle 7^{7^7}=(10-3)^{7^7}=\sum_{k=0}^{7^7}{7^7 \choose k}(10)^{7^7-k}(-3)^k=10m_1-3^{7^7}\) where \(\displaystyle m_1\in\mathbb{N}\)

Thus, the digit we seek will be the last digit of \(\displaystyle 3^{7^7}\) subtracted from 10.

Next, we see, via the binomial theorem, that:

\(\displaystyle 7^7=(8-1)^7=\sum_{k=0}^{7}{7 \choose k}(8)^{7-k}(-1)^k=4m_2-1\) where \(\displaystyle m_1\in\mathbb{N}\)

Observing that:

\(\displaystyle 3^{4(1)-1}=27\)

\(\displaystyle 3^{4(2)-1}=2187\)

We may choose to state the induction hypothesis $P_n$:

\(\displaystyle 3^{4n-1}=10k_n+7\)

As the induction step, we may add:

\(\displaystyle 3^{4(n+1)-1}-3^{4n-1}=80\cdot3^{4n-1}=80\left(10k_n+7 \right)\)

to get:

\(\displaystyle 3^{4(n+1)-1}=80\left(10k_n+7 \right)+10k_n+7=10\left(8\left(10k_n+7 \right)+k_n \right)+7\)

If we make the recursive definition:

\(\displaystyle k_{n+1}\equiv8\left(10k_n+7 \right)+k_n\) where \(\displaystyle k_1=2\)

we then have:

\(\displaystyle 3^{4(n+1)-1}=10k_{n+1}+7\)

We have derived $P_{n+1}$ from $P_n$ thereby completing the proof by induction.

Thus, we may conclude that the last digit of $7^{7^7}$ is $10-7=3$.

Alternate solution 1 (from anemone):

Spoiler

We write down the first few powers of 7 and notice that

\(\displaystyle 7^1=7,\;\;7^2=49,\;\;7^3=243,\;\;7^4=2401,\;\;7^5=16807,\;\;7^6=117649,\;\;7^7=823543,\;\;7^8=5764801,\cdots\)

There is a pattern of the last digit of the powers of 7, as they keep repeating themselves in the sequence 7, 9, 3, and 1.

Last digit of \(\displaystyle 7^n\)	7	9	3	1
n	1	2	3	4
	5	6	7	8
	...	...	...	...
	...	...	823543	...
	...	...	...	...

And our aim is to find the last digit of the number \(\displaystyle 7^{7^7}\), i.e. \(\displaystyle 7^{823543}\).

And this can be found out by dividing the number 823543 by 4 and then judging the location of it in the above table by looking at its remainder.

\(\displaystyle \frac{823543}{4}=205883\frac{3}{4}\)

Hence, we know that \(\displaystyle 7^{7^7}=7^{823543}\) lies in the third column in the table, which has 3 as its last digit.

Alternate solution 2 (from Opalg):

Spoiler

Start with the fact that $7^2 = 49$, which is $1$ short of a multiple of $10$. In the language of modular arithmetic, $7^2 = -1\pmod{10}$. Therefore $7^4 = (7^2)^2 = (-1)^2 = 1 \pmod{10}$. It follows that for any integers $x$ and $k$, $7^{x-4k} = 7^x(7^4)^k = 7^x1^k = 7^x \pmod{10}.$ [That says that if you change $x$ by a multiple of $4$ then the last digit of $7^x$ stays the same.]

Putting $x = 7^7$, it follows that if you want to know the value of $7^{7^7} \pmod{10}$, then you need to find the value of $7^7 \pmod4$. But $7 = -1 \pmod4$. So $7^7 = (-1)^7 = -1 = 3 \pmod4.$ Therefore $7^{7^7} = 7^3 = 49*7 = (-1)*7 = -7 = 3 \pmod{10}$. That says that the last digit of $7^{7^7}$ is $\Large \mathbf 3$.