Towers of Powers

Number Theory Level 5

Given a sequence of positive integers $a_1, a_2, a_3, \ldots, a_n$ , define the power tower function $f(a_1,a_2,a_3,\ldots,a_n)=a_1^{a_2^{a_3^{\ldots^{a_n}}}}$ Let $b_1, b_2, b_3, \ldots, b_{2017}$ be positive integers such that for any $i$ between $1$ and $2017$ inclusive, $f(a_1, a_2, a_3 \ldots, a_i, \ldots, a_{2017}) \equiv f(a_1, a_2, a_3 \ldots, a_i+b_i, \ldots, a_{2017}) \pmod{2017}$ for all sequences $a_1, a_2, a_3, \ldots, a_{2017}$ of positive integers greater than $2017$ . Find the smallest possible value of $b_1+b_2+b_3+\ldots+b_{2017}$ .

The answer is 6072.

1 solution

Stephen Brown
Nov 9, 2017

The solution involves the Carmichael function $\lambda (n)$ , which gives the smallest number $m$ for which, given $a$ coprime to $n$ , the equation

$a^m \equiv 1\,(mod\,n)$

always holds. The Carmichael function satisfies the relation

$a^x \equiv a^y\,(mod\,n) \Rightarrow x \equiv y\,(mod\,\lambda (n))$

Now we have:

$a_{1}^{n} \equiv (a_{1}+b_{1})^{n}\,(mod\,2017) \Rightarrow a_{1} \equiv a_{1}+b_{1}\,(mod\,2017) \Rightarrow b_1 = 2017$ $a_{1}^{a_{2}^{n}} \equiv a_{1}^{(a_{2}+b_{2})^{n}}\,(mod\,2017) \Rightarrow a_{2}^{n} \equiv (a_{2}+b_{2})^{n}\,(mod\,\lambda(2017)) \Rightarrow b_2 = 2016$

And so on. Thus we have that $b_{n} = \lambda^{n-1}(2017)$ , where n refers to the number of repeated applications of the Carmichael function. After four applications, we find $b_5 = 1$ , and since $\lambda (1) = 1$ , we have

$(b_1,b_2,b_3,...,b_{2017}) = (2017,2016,24,2,1,1,1,...,1)$

So the solution is $2017+2016+24+2+2013 = \boxed{6072}$

(This proof is not completely rigorous but is roughly the path to the correct answer)

Towers of Powers

The answer is 6072.

1 solution

0 pending reports