|
Let a, b, m be integers. To indicate that a and b have the same remainders modulo m, we write "a = b (m)", in words "a congruent b modulo m". See Wikipedia article on congruence relations
Part 1: The last digit is 3. To determine the last digit of a power, we must calculate its remainder modulo 10. Let's write down the remainders of 7^n modulo 10:
7^0 = 1 (10)
7^1 = 7 (10)
7^2 = 9 (10)
7^3 = 3 (10)
7^4 = 1 (10)
We see that the remainder series is periodic with period length 4. We conclude
(1) 7^n = 3 (10) <=> n = 3 (4).
Likewise we now examine the remainders modulo 4:
7^0 = 1 (4)
7^1 = 3 (4)
7^2 = 1 (4)
and conclude
(2) 7^n = 3 (4) <=> n = 1 (2).
We also know that
(3) 7^n = 1 (2) for all n.
Putting (1), (2) and (3) together, we see that 7^^3 = 7^(7^7) fullfills (1), (2) and (3), i.e.
7^^3 = 3 (10) and 7^^3 = 3 (4) and 7^^3 = 1 (2)
It follows by induction that
7^^n = 3 (10) and 7^^n = 3 (4) and 7^^n = 1 (2)
for all n>=3.
In other words, 3 is the last digit of 7^^n for all n>=3 and therefore also of 7^^7.
Part 2: The series of last integers always gets stationary, i.e. the period length is always 1. To see this, let's develop a method to determine the last digit of a^^n for sufficiently large n. First observe that the method we used for part 1 can be applied to any integer a: The series of remainders modulo 10 of a=a^1, a^2, a^3,... eventually becomes periodic with a period length smaller than a. Therefore, the last digit of a^M with sufficiently large M only depends on the remainder of M modulo this period length. Now let's say we have a candidate for the last digit d_0 of a^^n with sufficiently large n, then we can work backwards to figure out if this digit works:
(1) a^^n = d_0 (10) <=> a^^(n-1) = d_1 (m_1) for a certain m_1<10 and d_1<m_1
(2) a^^(n-1) = d_1 (m_1) <=> a^^(n-2) = d_2 (m_2) for a certain m_2<m_1 and d_2<m_2
...and so forth. The m_i's and d_i's are calculated by simply writing down the powers modulo m_(i-1) until they become periodic (With m_0:=10); m_i is the period length and d_i is the remainder that makes the left hand equation work. (There may be several d_i's which work; in that case we'd have to continue the recursion for all of them, but the method works anyhow) Since the series m_0, m_1,... decreases, we eventually arrive at an equation modulo m_i that either always holds or is always wrong. If we arrive at an equation that is always wrong, we know that our digit d_0 cannot possibly be the last digit of a^^n when n is large enough. By trying all digits from 0 to 9 we eventually find one that works.
|
