Consider the sequence t0 = 3, t1 = 3^3, t2 = 3^3^3 , t3 = 3^3^3^3,….. , defined by t0 = 3 and tn+1 = 3tn for n ≥ 0.
What are the last 2 digits of t3 = 3^3^3^3 ?
Show that the last 10 digits of tk are the same for all k ≥ 10
To find the last two digits of t3 = 3^3^3^3, we need to calculate the value of t3 and then find the remainder when dividing by 100 (since we want the last two digits).
To start, let's find the value of t1, t2, and t3 step by step:
t0 = 3
t1 = 3^3 = 27
t2 = 3^(3^3) = 3^27 ≈ 7,625,597,484,987 (a very large number)
t3 = 3^(3^(3^3))
Calculating t2 itself is a very large task, but we can represent it using modular arithmetic to simplify our calculations.
When we take any number modulo x, it means we divide the number by x and keep the remainder. For example, 15 modulo 10 is 5 (because 15 divided by 10 leaves a remainder of 5).
Now, let's observe the pattern of t1 and t2 modulo 100 (to find the last two digits):
t1 ≡ 27 (mod 100)
t2 ≡ 3^27 (mod 100)
To find t2 modulo 100, we can apply a property of modular arithmetic called the "exponentiation by squaring" method. This method allows us to simplify calculations by reducing the exponent.
In this case, we can use the property: (a^b) ≡ ((a^(b-phi(m))) mod m) when a and m are coprime.
Since 3 and 100 are coprime, we can rewrite t2 modulo 100 as:
t2 ≡ 3^(27 mod phi(100)) (mod 100)
To calculate phi(100), we need to find the totient function, which gives us the count of numbers less than 100 and coprime to 100. In this case, phi(100) = 40.
So, t2 modulo 100 becomes:
t2 ≡ 3^(27 mod 40) (mod 100)
Now we can simplify the exponent using the modular property:
27 mod 40 ≡ 27 (mod 40)
Now we have:
t2 ≡ 3^27 (mod 100)
To further simplify this, we can break down 3^27 into powers of 3 modulo 100 (due to the modular property):
t2 ≡ (3^20 * 3^7) (mod 100)
To calculate each part modulo 100:
3^20 (mod 100) ≡ 1 (mod 100) [as 3^20 ends in 01]
3^7 (mod 100) ≡ 87 (mod 100) [calculated using exponentiation by squaring method]
Now we have:
t2 ≡ 1 * 87 (mod 100)
t2 ≡ 87 (mod 100)
So, the last two digits of t2 are 87.
To find t3 modulo 100, we use the same method:
t3 ≡ 3^(t2 mod phi(100)) (mod 100)
t2 mod phi(100) = 87 mod 40 = 7
Therefore:
t3 ≡ 3^7 (mod 100)
Using the exponentiation by squaring method:
3^7 (mod 100) ≡ 87 (mod 100)
Thus, the last two digits of t3 are also 87.
Now, let's move on to showing that the last 10 digits of tk are the same for all k ≥ 10.
To prove this, we need to establish the pattern of the last 10 digits of tn as we increase n. We'll consider two consecutive terms, tn and tn+1.
Let's assume that tn has the same last 10 digits for some k (k ≥ 10).
We can write tn as: tn = (10^10 * x) + d, where x represents the digits before the last 10 digits, and d represents the last 10 digits.
Using the given recurrence relation, tn+1 = 3tn, we can rewrite it as: tn+1 = 3((10^10 * x) + d).
Expanding the equation: tn+1 = 3 * 10^10 * x + 3d
Now we can observe the last 10 digits of tn+1. It will be given by d1 = 3d (modulo 10^10).
So, we have: tn+1 = (10^10 * x) + d1
This shows that tn+1 has the same last 10 digits as tn, as long as tn had the same last 10 digits initially.
Since t10 has been computed and has the same last 10 digits as t3, we can conclude that all tk (k ≥ 10) will have the same last 10 digits.
In summary, the last two digits of t3 = 3^3^3^3 are 87, and the last 10 digits of tk are the same for all k ≥ 10.