Prove that for an integer X that is not a multiple of 5, Xn Xn mod 4 (mod 5). (5 points)
Use this to compute, as e ciently as you can, 1234567 (mod 5). Show your steps. (2 points)
A fast way to generate large numbers is with power towers. The following are the rst few power towers of 2:
X1=2
X2=22=4
X3=222=24=16 (1)
X4 = 2222 = 216 = 65536
X5 = 22222 = 265536:
As you can see, these numbers get large fast. But even for these incredibly large numbers, we can still compute and determine things about them. Let Xk be the k-th power tower of 2.
{ How many digits (base-10) does X5 have? Give an exact value. (1 points) { Give a recursive formulation for Xk+1 in terms of Xk. (2 points)
{ Prove that for all su ciently large k, Xk 1 (mod 5). (5 points) { Prove that for all su ciently large k, Xk 0 (mod 2). (2 points)
{ Based on the previous results, compute the 1s digit of the k-th power tower for all su ciently large k. (8 points)
Prove that for any integer value of D, the equation 27x + 14y = D has integer solutions for x and y. (10 points)
Consider the equation 27x + 14y + 10z = 1. Give parameterized solutions for all integer solutions x; y; z. How many parameters do you need? Hint: What does this equation represent, geometrically? (8 points)
Consider the following system of equations:
27x + 14y + 10z = 1
(2)
3x + 5y + 7z = 1:
Are there any integer solutions to this system of equations? If so, what are they? Hint: What does the solution to this system of equations represent, geometrically? (7 points)
Bonus: For a = 1; 2; 3; 4; 5; 6; 7; 8; 9, determine what the 1s digit of the k-th power tower base-a is, for all su ciently large k.
1
