MathDB
Problems
Contests
National and Regional Contests
Switzerland Contests
Switzerland - Final Round
2023 Switzerland - Final Round
3
3
Part of
2023 Switzerland - Final Round
Problems
(1)
Gcd of some consecutive terms of a recursive sequence
Source: Swiss MO 2023/3
3/12/2023
Let
x
,
y
x,y
x
,
y
and
a
0
,
a
1
,
a
2
,
⋯
a_0, a_1, a_2, \cdots
a
0
,
a
1
,
a
2
,
⋯
be integers satisfying
a
0
=
a
1
=
0
a_0 = a_1 = 0
a
0
=
a
1
=
0
, and
a
n
+
2
=
x
a
n
+
1
+
y
a
n
+
1
a_{n+2} = xa_{n+1}+ya_n+1
a
n
+
2
=
x
a
n
+
1
+
y
a
n
+
1
for all integers
n
≥
0
n \geq 0
n
≥
0
. Let
p
p
p
be any prime number. Show that
gcd
(
a
p
,
a
p
+
1
)
\gcd(a_p,a_{p+1})
g
cd
(
a
p
,
a
p
+
1
)
is either equal to
1
1
1
or greater than
p
\sqrt{p}
p
.
number theory
greatest common divisor