MathDB

5

Part of 1999 Dutch Mathematical Olympiad

Problems(1)

a[n] = n^2 + c

Source: Dutch NMO 1999

10/22/2005
Let cc be a nonnegative integer, and define an=n2+ca_n = n^2 + c (for n≥1)n \geq 1). Define dnd_n as the greatest common divisor of ana_n and an+1a_{n + 1}. (a) Suppose that c=0c = 0. Show that dn=1, ∀n≥1d_n = 1,\ \forall n \geq 1. (b) Suppose that c=1c = 1. Show that dn∈{1,5}, ∀n≥1d_n \in \{1,5\},\ \forall n \geq 1. (c) Show that dn≤4c+1, ∀n≥1d_n \leq 4c + 1,\ \forall n \geq 1.
algorithmgreatest common divisornumber theoryEuclidean algorithm