MathDB

Sequence with GCD involved

Source: 2021 Simon Marais, A2

November 2, 2021

Sequencenumber theorygreatest common divisor

Problem Statement

Define the sequence of integers

a_1, a_2, a_3, \ldots

by

a_1 = 1

, and

a_{n+1} = \left(n+1-\gcd(a_n,n) \right) \times a_n

for all integers

n \ge 1

. Prove that

\frac{a_{n+1}}{a_n}=n

if and only if

n

is prime or

n=1

. Here

\gcd(s,t)

denotes the greatest common divisor of

s

and

t

.

Back to Problems View on AoPS