MathDB

a[n] = n^2 + c

Source: Dutch NMO 1999

October 22, 2005

algorithmgreatest common divisornumber theoryEuclidean algorithm

Problem Statement

Let

c

be a nonnegative integer, and define

a_n = n^2 + c

(for

n \geq 1)

. Define

d_n

as the greatest common divisor of

a_n

and

a_{n + 1}

. (a) Suppose that

d_n \in \{1,5\},\ \forall n \geq 1

. Show that

d_n = 1,\ \forall n \geq 1

. (b) Suppose that

c = 1

. Show that

d_n \in \{1,5\},\ \forall n \geq 1

. (c) Show that

d_n \leq 4c + 1,\ \forall n \geq 1

.

Back to Problems View on AoPS