Solution: Day 5, problem 2

The sequence ( u_n ) starts 5/4, 51/14, 277/20, 1497/26, 4045/16, ... It is required to show that the first integral u_n is u_2755452 = 10^2019025 (approx). The first step is to note that the numbers U_n = (6n + 2)u_n satisfy the recursion relation U_n+3 = U_n + 2U_n+1 + 5U_n+2 (the proof is elementary and I omit it) and hence are all integral. One must thus show that the congruence U_n = 0 modulo (6n + 2) holds for n₀ = 2755452 and for no smaller value of n. (To find the approximate size of u_n0 is then easy since the explicit solution of the recursion gives U_n ~ ABⁿ with A = 1.75487766624669276 ... , B = 5.40431358073618481197 ... .) Again the detailed proof is complicated and I skip it, mentioning only that this is in the same category as the problem of finding pseudoprimes (for instance, a 2-pseudoprime is a composite integer n for which the number 2^n-1 = 1 modulo n, and this is a similar condition to the integrality of u_n since the numbers 2^{n-1 - 1 satisfy a linear recursion T_n+2 = 3T_n+1 - 2T_n similar to that of the U_n) and can be analyzed by studying the splitting behavior of the cubic polynomial X3 - 5X2 - 2X - 1 modulo varying primes.}

Don Zagier 1996