Let $p, q$ be coprime integers, such that $|\frac{p} {q}| \leq 1$. For which $p, q$, there exist even integers $b_1, b_2, \ldots, b_n$, such that $$\frac{p} {q}=\frac{1}{b_1+\frac{1}{b_2+\frac{1}{b_3+\ldots}}}? $$
Problem
Source: Bulgarian Autumn Tournament 2023, 9.4
Tags: number theory
19.11.2023 21:06
https://arxiv.org/pdf/1009.1800.pdf (Lemma 2, only the existence part)
20.11.2023 13:12
I did the sufficiency part but the other way wasn't accepted (I got scammed) and only got 4/7 points
25.11.2023 20:05
Set $ b_i=2\ell_i$, all of them are even. At the first step we get the pairs $$ \displaystyle A:= \{(p,q) : (p,q)=(1,2\ell_1), \ell_1\in \mathbb{Z}.\qquad(1).$$At each subsequent step we expand the set $ A$ by adding additional pairs $ (p', q')$ defined as $$ \displaystyle \left\{(p',q') : \frac{p'}{q'}=\frac{1}{2\ell +\frac{p}{q}}, (p,q)\in A, \ell\in\mathbb{Z} \right\}\qquad(2).$$By $ (2)$ we obtain $$ \displaystyle p'=q\,;\, q'=2\ell q + p \quad(3)$$So, if $ (p,q)$ is obtained in the process of expanding, we also add $ (p',q')$ defined as in $ (3)$, We want to characterize all pairs $ (p,q)$ that can be obtained in this way. Note that if $ (p,q)=1$, then from $ (3)$ follows $ (p',q')=1$. Let us prove that the set of pairs $(p,q)$ in question is $$ \displaystyle A:=\left\{(p,q) : p,q\in\mathbb{Z}\setminus\{0\}, |p|<|q|,(p,q)=1, \text{ one of } p,q \text{ is even, the other is odd.} \right\}$$Note that we ruled out $ |p|=|q|$ because $ \frac{p}{q}=\pm1$ cannot be represented as wanted. The transformation described in $(3)$ shows that we cannot step outside $ A$. To prove that all pairs in $ A$ can be generated, we follow a standard procedure - take $(p',q')\in A$ and search for $ (p,q)\in A$ that generates $ (p',q')$ via $ (3),$ but we want $ (p,q)$ be "less" than $ (p',q').$ That's how induction works. Solving $ (3)$ with respect to $ (p,q)$ yields $$\displaystyle p=q'-2\ell p'\,;\, q=p' \qquad(4)$$Clearly, we can choose $ \ell\in \mathbb{Z}$ such that $ |q'-2\ell p'|< |p'|$ (since $ p'\neq 0$). Indeed, consider the points $ q'-2\ell p'$ where $ \ell$ runs through all integers. These points are at a distance $ 2p'$ apart, and none of them hits $ p'$ because $ (p',q')=1.$ Hence, the point closest to $ 0$ has magnitude less than $ p'.$ So, we started from $ (p',q')\in A$, and found $ (p,q)\in A$ that generates $ (p',q')$ and moreover, $ q=p', |p|< |p'|<|q'|.$ Apparently $ (p,q)$ is "less" than $ (p',q'),$ that is, $ |p|<|p'|, |q|<|q'|.$ Now, induction does the job. Obviously, $ (1,2), (-1,2), (1,-2), (-1,-2)$ can be represented as continued fractions satisfying the statement. Assume that all $ (p,q)\in A$ with $ |p|\le N, |q|\le N$ can be represented like that. Take $ (p',q')\in A, |q'|=N+1.$ As just shown, there exists $ (p,q)\in A, |p|<|q|\le N$ such that $$ \displaystyle \frac{p'}{q'}=\frac{1}{2\ell+\frac{p}{q} }.$$The induction step is complete and the result follows. Note that it also follows that the representation of numbers in $A$ as continued fractions like that is unique. Indeed, take a pair $ (p',q')\in A.$ The pair $ (p,q)\in A$ that satisfies $ (4)$ and $ |p|<|p'|$ is determined uniquely. Uniqueness follows easily. Remark. The main difficulty in my opinion is that the the answer wasn't told to the students. The result could have been much better otherwise. Some motivation about guessing the answer can be found in my blog.