Maths Olympiad Prep

Library / /10 of 14

Number theory Difficulty 6.2 National olympiad Prove it Bulgaria

Let p,qp, q be coprime integers, such that pq1\frac{p}{q} \le 1. For which p,qp, q, there exist even integers b1,b2,,bnb_1, b_2, \dots, b_n, such that
pq=1b1+1b2+1b3+? \frac{p}{q} = \frac{1}{b_1 + \frac{1}{b_2 + \frac{1}{b_3 + \dots}}}?

Solution

Set bi=2ib_i = 2\ell_i, all of them are even. At the first step we get the pairs
A:={(p,q):(p,q)=(1,21),1Z.(1)}. A := \{(p, q) : (p, q) = (1, 2\ell_1), \ell_1 \in \mathbb{Z}. \quad (1)\}.
At each subsequent step we expand the set AA by adding additional pairs (p,q)(p', q')
defined as
{(p,q):pq=12+pq,(p,q)A,Z}(2). \left\{ (p', q') : \frac{p'}{q'} = \frac{1}{2\ell + \frac{p}{q}}, (p, q) \in A, \ell \in \mathbb{Z} \right\} \quad (2).
By (2) we obtain
p=q;q=2q+p(3) p' = q; \quad q' = 2\ell q + p \quad (3)
So, if (p,q)(p, q) is obtained in the process of expanding, we also add (p,q)(p', q') defined as in (3). We want to characterize all pairs (p,q)(p, q) that can be obtained in this way. Note that if (p,q)=1(p, q) = 1, then from (3) follows (p,q)=1(p', q') = 1. Let us prove that the set of pairs (p,q)(p, q) in question is
A:={(p,q):p,qZ{0},p<q,(p,q)=1, one of p,q is even, the other is odd.} A := \{(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.}\}
Note that we ruled out p=q|p| = |q| because pq=±1\frac{p}{q} = \pm 1 cannot be represented as wanted. The transformation described in (3) shows that we cannot step outside AA. To prove that all pairs in AA can be generated, we follow a standard procedure - take (p,q)A(p', q') \in A and search for (p,q)A(p, q) \in A that generates (p,q)(p', q') via (3), but we want (p,q)(p, q) be "less" than (p,q)(p', q'). That's how induction works. Solving (3) with respect to (p,q)(p, q) yields
p=q2p;q=p(4) p = q' - 2\ell p'; \quad q = p' \quad (4)
Clearly, we can choose Z\ell \in \mathbb{Z} such that q2p<p|q' - 2\ell p'| < |p'| (since p0p' \neq 0). Indeed, consider the points q2pq' - 2\ell p' where \ell runs through all integers. These points are at a distance 2p2p' apart, and none of them hits pp' because (p,q)=1(p', q') = 1. Hence, the point closest to 0 has magnitude less than pp'. So, we started from (p,q)A(p', q') \in A, and found (p,q)A(p, q) \in A that generates (p,q)(p', q') and moreover, q=p,p<p<qq = p', |p| < |p'| < |q'|. Apparently (p,q)(p, q) is "less" than (p,q)(p', q'), that is, p<p,q<q|p| < |p'|, |q| < |q'|. Now, induction does the job. Obviously, (1,2),(1,2),(1,2),(1,2)(1, 2), (-1, 2), (1, -2), (-1, -2) can be represented as continued fractions satisfying the statement. Assume that all (p,q)A(p, q) \in A with pN,qN|p| \le N, |q| \le N can be represented like that. Take (p,q)A,q=N+1(p', q') \in A, |q'| = N + 1. As just shown, there exists (p,q)A,p<qN(p, q) \in A, |p| < |q| \le N such that
pq=12+pq. \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 AA as continued fractions like that is unique. Indeed, take a pair (p,q)A(p', q') \in A. The pair (p,q)A(p, q) \in A that satisfies (4) and p<p|p| < |p'| is determined uniquely. Uniqueness follows easily.

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.