Maths Olympiad Prep

Library / Ukrainian Mathematical Competitions /3 of 6

Ukrainian Mathematical Competitions

Number theory Difficulty 5.2 AIME, harder Prove it Ukraine

Let's consider the sequence of positive integers (xn)(x_n), that is given by the formula:
xn=5⋅2n−1x_n = 5 \cdot 2^n - 1, n∈Nn \in N. Prove, that there is an infinite number of pairs (xi,xj)(x_i, x_j) of elements that are mutually-prime, and at the same time none of the elements xkx_k in this infinite sequence of pairs is included at the initial sequence infinite number of times.
(Bogdan Rublyov)

Solution

Everything follows from this equation: ∀n∈N\forall n \in N
xn+1−2xn=5⋅2n+1−1−2⋅(5⋅2n−1)=10⋅2n−1−10⋅2n+2=1. x_{n+1} - 2x_n = 5 \cdot 2^{n+1} - 1 - 2 \cdot (5 \cdot 2^n - 1) = 10 \cdot 2^n - 1 - 10 \cdot 2^n + 2 = 1.
So, GCF of (xn+1,xn)(x_{n+1}, x_n) is a divisor of 11, what means that they're coprime. What had to be shown.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.