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 a_j denote a tower of j 2s: 2^22.·'2. Prove that a_n = a_n-1 (mod n).

I was able to prove it using little more than Euler's formula that 2^Phi(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:

• j = 2: a_j = 4 and a_j-1 = 2. They are congruent mod 1 and 2, but not 3 (so B-5 as stated is best possible).
• j = 3: a_j = 16 and a_j-1 = 4; they are congruent mod 1, 2, 3, and 4, but not 5.
• j = 4: First failure at modulus 11.
• j = 5: First failure at mod 23 (= 2*11 + 1)
• j = 6: First failure at mod 47 (= 2*47 + 1)
• j = 7: First failure at mod 283 (= 6*47 + 1)
• j = 8: First (I think) failure is at 1699 (= 6*1699+1)
• j = 9: First (I think) failure is at 1699*360 + 1

There seems to be some pattern here. In particular, it looks like B-5 can be strengthened at least to

If n > 3, then a_n = a_n-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.

Challenges:

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:

   a_j = a_j-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 a_j and a_j-1 are not congruent mod k.

---

More...I think I can define a simple TowerMod function. Recall that PowerMod[a,n,m] gives aⁿ mod m. My TowerMod gives a^aa.·'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.