Olympiad Maths Prep

Library / /2 of 2

Number theory Difficulty 6.6 National olympiad Prove it Bulgaria

For a positive integer nn, denote with b(n)b(n) the smallest positive integer kk, such that there exist integers a1,a2,,aka_1, a_2, \dots, a_k, satisfying n=a1a2+a2a3++aka1n = a_1^{a_2} + a_2^{a_3} + \dots + a_k^{a_1}. Determine whether the set of positive integers nn is finite or infinite, which satisfy:
a) b(n)=12;b) b(n)=121212. \text{a) } b(n) = 12; \quad \text{b) } b(n) = 12^{12^{12}}.

Solution

a) From Fermat's theorem and y21(mod67)y±1(mod67)y^2 \equiv 1 \pmod{67} \Leftrightarrow y \equiv \pm 1 \pmod{67} it follows that any student number gives a remainder of 00, 11 or 6666 when divided by 6767. Let us consider the numbers 1266k+112^{66k+1}, where kNk \in \mathbb{N}. They are presented as the sum of 1212 student numbers. Furthermore, by Fermat's theorem 1266k+112(mod67)12^{66k+1} \equiv 12 \pmod{67}. This shows that b(1266k+1)=12b(12^{66k+1}) = 12 for every kNk \in \mathbb{N}. Therefore, the set here is infinite.

b) For PZ[X]P \in \mathbb{Z}[X] let us set Δ(P)(x)=P(x+1)P(x)\Delta(P)(x) = P(x+1) - P(x). It is clear that if PP is of degree dd with leading coefficient aa, then Δ(P)Z[X]\Delta(P) \in \mathbb{Z}[X] is a polynomial of degree d1d-1 with leading coefficient adad. Consider the series of polynomials P1(x)=x33P_1(x) = x^{33}, Pk+1=Δ(Pk)P_{k+1} = \Delta(P_k) for kNk \in \mathbb{N}. It is easy to see by induction on kk that for each xZx \in \mathbb{Z}, kNk \in \mathbb{N} the number Pk(x)P_k(x) is a sum of 2k12^{k-1} student numbers. Furthermore, we have that P33(x)=33!x+bP_{33}(x) = 33!x + b for some bZb \in \mathbb{Z}. Since 11 and 1-1 are student numbers, each integer is the sum of at most 232+33!<1212122^{32} + 33! < 12^{12^{12}} student numbers. Then the set here is empty, and therefore finite.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.