Library / /36 of 57

, 2007

Number theory Difficulty 6.1 National Olympiad Prove it JBMO

Problem:
Let $a$ , $b$ be two co-prime positive integers. A number is called good if it can be written in the form $a x + b y$ for non-negative integers $x$ , $y$ . Define the function $f: \mathbb{Z} \rightarrow \mathbb{Z}$ as $f(n) = n - n_{a} - n_{b}$ , where $s_{t}$ represents the remainder of $s$ upon division by $t$ . Show that an integer $n$ is good if and only if the infinite sequence $n, f(n), f(f(n)), \ldots$ contains only non-negative integers.

Solution

Solution:
If $n$ is good then $n = a x + b y$ . Also $n_{a} = (b y)_{a}$ and $n_{b} = (a x)_{b}$ so
$f(n) = a x - (a x)_{b} + b y - (b y)_{a} = b y' + a x'$
is also good, thus the sequence contains only good numbers which are non-negative.

Now we have to prove that if the sequence contains only non-negative integers then $n$ is good. Because the sequence is non-increasing, the sequence will become constant from some point onwards. But $f(k) = k$ implies that $k$ is a multiple of $a b$ , thus some term of the sequence is good. We are done if we prove the following:

Lemma: $f(n)$ is good implies $n$ is good.

Proof of Lemma: $n = 2 n - n_{a} - n_{b} - f(n) = a x' + b y' - a x - b y = a(x' - x) + b(y' - y)$ and $x' \geq x$ because $n \geq f(n) \Rightarrow n - n_{a} \geq f(n) - f(n)_{a} \Rightarrow a x' \geq a x + b y - (b y)_{a} \geq a x$ . Similarly $y' \geq y$ .

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 reproduced verbatim; metadata (topic, difficulty) added by this project.