Define the function f on the natural numbers by f(1) = 2, f(n) = 2f(n-1). Show that f(n) has the same residue mod m for all sufficiently large n.
Solution
This is the so-called tower of exponents, but HTML is not up showing it! The trick is to use induction on m (which is not at all obvious). The result is trivial for m = 1.
If m is even, then we can write m = 2ab, where b is odd. Then f(n) is eventually constant mod b. Obviously f(n) is eventually 0 mod 2a, so the residue mod m is eventually constant.
If m is odd, then 2φ(m) = 1 mod m, where φ(m) < m. So by induction f(n) is eventually constant mod φ(m). Hence f(n+1) = 2f(n) is eventually constant mod m.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002