Yesterday, I challenged you to prove that
where , , and the are defined by and .
The proof is by induction on . The base case is just arithmetic:
Now suppose that we already know the statement holds for some particular ; we must show that it also holds for . The proof is not too hard, but we have to handle the stacked exponents with care! (Note also that all the following equalities are really taken , which is OK since addition, subtraction, and multiplication are all compatible with taking remainders.)
(The last step is because we know from yesterday that .) So , which is what we wanted to show.