MathDB
Problems
Contests
National and Regional Contests
Germany Contests
QEDMO
2007 QEDMO 5th
1
1
Part of
2007 QEDMO 5th
Problems
(1)
Easy number theory: 3 coprime pairs yield infinitely many
Source: 5th QEDMO problem 1, proposed by me
11/10/2007
Let
a
a
a
,
b
b
b
and
k
k
k
be three positive integers. We define two sequences
(
a
n
)
\left( a_{n}\right)
(
a
n
)
and
(
b
n
)
\left( b_{n}\right)
(
b
n
)
by the starting values a_{1}\equal{}a and b_{1}\equal{}b and the recurrent equations a_{n\plus{}1}\equal{}ka_{n}\plus{}b_{n} and b_{n\plus{}1}\equal{}kb_{n}\plus{}a_{n} for each positive integer
n
n
n
. Prove that if
a
1
⊥
b
1
a_{1}\perp b_{1}
a
1
⊥
b
1
,
a
2
⊥
b
2
a_{2}\perp b_{2}
a
2
⊥
b
2
and
a
3
⊥
b
3
a_{3}\perp b_{3}
a
3
⊥
b
3
hold, then
a
n
⊥
b
n
a_{n}\perp b_{n}
a
n
⊥
b
n
holds for every positive integer
n
n
n
. Here, the abbreviation
x
⊥
y
x\perp y
x
⊥
y
stands for "the numbers
x
x
x
and
y
y
y
are coprime".
modular arithmetic