Track / Stage 5 / 83 of 400 #1163 of 2444

Problem 1163

AIME late

Number theory Difficulty 5.1 Prove it Saudi Arabian Mathematical Competitions · Saudi Arabia · 2012

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$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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$ .

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