Problem

Source: Dutch NMO 2022 p3

Tags: algebra, simplify, simplification, number theory



Given a positive integer $c$, we construct a sequence of fractions $a_1, a_2, a_3,...$ as follows: $\bullet$ $a_1 =\frac{c}{c+1} $ $\bullet$ to get $a_n$, we take $a_{n-1}$ (in its most simplified form, with both the numerator and denominator chosen to be positive) and we add $2$ to the numerator and $3$ to the denominator. Then we simplify the result again as much as possible, with positive numerator and denominator. For example, if we take $c = 20$, then $a_1 =\frac{20}{21}$ and $a_2 =\frac{22}{24} = \frac{11}{12}$ . Then we find that $a_3 =\frac{13}{15}$ (which is already simplified) and $a_4 =\frac{15}{18} =\frac{5}{6}$. (a) Let $c = 10$, hence $a_1 =\frac{10}{11}$ . Determine the largest $n$ for which a simplification is needed in the construction of $a_n$. (b) Let $c = 99$, hence $a_1 =\frac{99}{100}$ . Determine whether a simplification is needed somewhere in the sequence. (c) Find two values of $c$ for which in the first step of the construction of $a_5$ (before simplification) the numerator and denominator are divisible by $5$.