- MacTutor History of Mathematics

Solution: Day 5, problem 2

The solutions of the fifth day problems problems are somewhat longer and we only give highlights.

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}

u_{2755452}

= 102019025 (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_{0} = 2755452

and for no smaller value of

n

.
(To find the approximate size of

u_{n¬0}

is then easy since the explicit solution of the recursion gives

U_{n} ~ AB^{n}

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 mod 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

X^{3} - 5X^{2} - 2X - 1

modulo varying primes.