Power Tower and Carmichael Lambda Function

*To*: mathgroup at smc.vnet.net*Subject*: [mg89662] Power Tower and Carmichael Lambda Function*From*: "John Snyder" <jsnyder at wi.rr.com>*Date*: Tue, 17 Jun 2008 00:36:51 -0400 (EDT)

On New Year's Day of this year the following problem was published in a problem contest on an internet website asking for the last four digits of the following number: 2008^(2007^(2006^.^.^.^(2^1))) For some reason I got interested in the problem (it isn't homework, I am 58 years old) and I solved it using Mathematica's CarmichaelLambda function as follows: In[9]:= lambda=FoldList[CarmichaelLambda[#1]&,10000,Range[6]] Out[9]= {10000,500,100,20,4,2,1} In[10]:= m=Range[2002,2008]//Reverse Out[10]= {2008,2007,2006,2005,2004,2003,2002} In[11]:= Mod @@@ Transpose[{m, lambda}] Out[11]= {2008,7,6,5,0,1,0} Now, since the tower of powers is evaluated from the top down I reasoned that everything from the top down through the 5 contributed nothing to the answer because 5^0=1. I got my answer doing the following: In[12]:= PowerMod[2008,7^6,10000] Out[12]= 5328 When the solution was finally published the other day the following result was listed as being the correct solution: In[13]:= PowerMod[2008,7^6^5,10000] Out[13]= 1008 It seems to me that the relevant exponent should be just 7^6, not 7^6^5 because 5^0=1. Playing around with some smaller and easier numbers in Mathematica I think I am correct, but the problem site says otherwise. I am no expert in number theory so could someone who is please explain to me which answer is correct and why? Does Mathematica really use the parentheses in the exponent in evaluating something like this? Thanks, John

**Follow-Ups**:**Re: Power Tower and Carmichael Lambda Function***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>