Library / /47 of 120

, 2012

Number theory Difficulty 5.1 AIME, harder Prove it Saudi Arabia

Let $a$ , $b$ , $c$ , $d$ be integers with $a$ , $c$ both nonzero, and define $x_n = \gcd(an + b, cn + d)$ for all positive integers $n$ . Show that the sequence $x_1, x_2, x_3, \dots$ is unbounded if and only if $ad = bc$ .

Solution

Note that
$\begin{aligned} \frac{\gcd(acn + bc, acn + ad)}{ac} &\le \gcd(an + b, cn + d) \\ &\le \gcd(acn + bc, acn + ad). \end{aligned}$
Suppose $ad = bc$ . We have
$\begin{aligned} \gcd(an + b, cn + d) &\ge \frac{\gcd(acn + bc, acn + ad)}{ac} \\ &= \frac{\gcd(acn + bc, acn + bc)}{ac} \\ &= n + \frac{b}{a}. \end{aligned}$
$n + \frac{b}{a}$ is unbounded, so $\gcd(an+b, cn+d)$ is also unbounded as desired.

On the other hand, suppose $ad \neq bc$ . Then $|ad - bc| \neq 0$ , so therefore
$\begin{aligned} \gcd(an + b, cn + d) &\le \gcd(acn + bc, acn + ad) \\ &= \gcd(acn + bc, ad - bc) \\ &\le |ad - bc|. \end{aligned}$
Therefore $\gcd(an+b, cn+d)$ is bounded above by a fixed number that is independent of $n$ .

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.