Problem of the Week 850

Putnam Problem Notes

Last Saturday [Decmeber 6] saw the annual Putnam competition. Since many on my PoW list do work on the Putnam problems, I am sending out this non-PoW mailing. The problems were nicely interesting, and B-5 especially caught my interest. This was the problem:

B-5: Let aj denote a tower of j 2s: 222.·'2. Prove that an = an-1 (mod n).

I was able to prove it using little more than Euler's formula that 2Phi(n) = 1 (mod n) when n is odd.

My proof was constructive in that it allowed me to write some Mathematica code to get, given j and m, the value of Mod[a_j, m]. It is always nice to see how to deal with such ridiculously large integers. And, naturally, computations lead to further questions, in particular, where does the congruence stop? Examples:

There seems to be some pattern here. In particular, it looks like B-5 can be strengthened at least to
If n > 3, then an = an-1 (mod k) for each k = 1, 2, 3, ..., n, n+1.
Now, I have to admit it is possible my code is incorrect, so these observations should be taken with a grain of salt.


  1. Prove the assertion about n+1 above. (This might make a nice journal submission if true; on the other hand, it might follow from the solution of B-5; I will have to look at that carefully. Right now my solution proves:
    aj = aj-1 (mod n) whenever j > n.
    And the present question is whether this can be extended to j > n - 1.)

  2. Say somethimg intelligent (either conjecture or proof) about the least k for which aj and aj-1 are not congruent mod k.

More...I think I can define a simple TowerMod function. Recall that PowerMod[a,n,m] gives an mod m. My TowerMod gives aaa.·'a (n terms) mod m.

This is still work-in-progress. As usual, I have more questions than answers.

I would love some independent confirmation of these computations so that I can know my code is correct.

© Copyright 1997 Stan Wagon. Reproduced with permission.

The Math Forum

2 October 1998