Maths Olympiad Prep

Library / /13 of 15

Number theory Difficulty 9.0 IMO level Prove it IMO

Let S\mathcal{S} be a finite nonempty set of prime numbers. Let 1=b1<b2<1 = b_{1} < b_{2} < \cdots be the sequence of all positive integers whose prime divisors all belong to S\mathcal{S}. Prove that, for all but finitely many positive integers nn, there exist positive integers a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} such that
a1b1+a2b2++anbn=1b1+1b2++1bn. \frac{a_{1}}{b_{1}} + \frac{a_{2}}{b_{2}} + \cdots + \frac{a_{n}}{b_{n}} = \left\lceil \frac{1}{b_{1}} + \frac{1}{b_{2}} + \cdots + \frac{1}{b_{n}} \right\rceil.

Solutions — 3

Solution 1

If S\mathcal{S} has only one element pp, then bi=pi1b_{i} = p^{i-1} and we can easily find a1,,ana_{1}, \ldots, a_{n} with 2=i=0n11pi=i=0n1aipi12 = \left\lceil \sum_{i=0}^{n-1} \frac{1}{p^{i}} \right\rceil = \sum_{i=0}^{n-1} \frac{a_{i}}{p^{i-1}} by taking a1=a2==an1=1a_{1} = a_{2} = \cdots = a_{n-1} = 1 and choosing an=pn1(p+p2++pn2)a_{n} = p^{n-1} - (p + p^{2} + \ldots + p^{n-2}).

More generally, observe that the sum of 1bi\frac{1}{b_{i}} over all ii is
i1bi=i(1+1pi+1pi2+)=pSpp1 \begin{aligned} \sum_{i} \frac{1}{b_{i}} &= \prod_{i} \left(1 + \frac{1}{p_{i}} + \frac{1}{p_{i}^{2}} + \ldots \right) \\ &= \prod_{p \in \mathcal{S}} \frac{p}{p-1} \end{aligned}
In particular, if nn is large enough, then
j=1n1bj=pSpp1 \left\lceil \sum_{j=1}^{n} \frac{1}{b_{j}} \right\rceil = \left\lceil \prod_{p \in \mathcal{S}} \frac{p}{p-1} \right\rceil
For the remainder of the proof, we will only consider nn large enough that this equality holds.

Next, we handle the special case S={2,3}\mathcal{S} = \{2,3\}, for which this product is 33. Start by setting
ai={1, if 2bibn2, if 2bi>bn a_{i} = \begin{cases}1, & \text{ if } 2 b_{i} \leqslant b_{n} \\ 2, & \text{ if } 2 b_{i} > b_{n}\end{cases}
Then,
inν3(bi)=taibi={23t, if bn3t0, otherwise  \sum_{\substack{i \leqslant n \\ \nu_{3}(b_{i}) = t}} \frac{a_{i}}{b_{i}} = \begin{cases} \frac{2}{3^{t}}, & \text{ if } b_{n} \geqslant 3^{t} \\ 0, & \text{ otherwise } \end{cases}
As a result,
inaibi=t03tbn23t=313T \begin{aligned} \sum_{i \leqslant n} \frac{a_{i}}{b_{i}} &= \sum_{\substack{t \geqslant 0 \\ 3^{t} \leqslant b_{n}}} \frac{2}{3^{t}} \\ &= 3 - \frac{1}{3^{T}} \end{aligned}
where TT is the largest t0t \geqslant 0 with 3tbn3^{t} \leqslant b_{n}. Thus, increasing aja_{j} by one (where bj=3Tb_{j} = 3^{T}) gives a sequence of aia_{i} that works.

Otherwise, we may assume that S>1|\mathcal{S}| > 1 and S{2,3}\mathcal{S} \neq \{2,3\}, which means that the product pSpp1\prod_{p \in \mathcal{S}} \frac{p}{p-1} is not an integer. Indeed,
- if S>2|\mathcal{S}| > 2 then 22 divides the denominator at least twice and so divides the denominator of the overall fraction;
- if S=2|\mathcal{S}| = 2 and 2S2 \notin \mathcal{S} then 22 divides the denominator and not the numerator;
- if S={2,p}\mathcal{S} = \{2, p\} then the product is 2p/(p1)2p/(p-1) which is not an integer for p>3p > 3.

It follows that for some fixed α>0\alpha > 0, we have that
pSpp1=pSpp1+α \left\lceil \prod_{p \in \mathcal{S}} \frac{p}{p-1} \right\rceil = \prod_{p \in \mathcal{S}} \frac{p}{p-1} + \alpha
from which it follows that
i=1n1bii=1n1bi>α \left\lceil \sum_{i=1}^{n} \frac{1}{b_{i}} \right\rceil - \sum_{i=1}^{n} \frac{1}{b_{i}} > \alpha
It will now suffice to prove the following claim.

Claim. Suppose that nn is large enough, and let epe_{p} be the largest nonnegative integer such that pepbnp^{e_{p}} \leqslant b_{n}. Let M=pSpepM = \prod_{p \in \mathcal{S}} p^{e_{p}}. If uu is a positive integer such that u/M>αu / M > \alpha, then there exist nonnegative integers aia_{i} such that
iaibi=uM. \sum_{i} \frac{a_{i}}{b_{i}} = \frac{u}{M}.
The problem statement follows after replacing aia_{i} with ai+1a_{i} + 1 for each ii.

To prove this, choose some constant cc such that pSpc<α\sum_{p \in \mathcal{S}} p^{-c} < \alpha, and suppose nn is large enough that pc<bnp^{c} < b_{n} for each pSp \in \mathcal{S}; in particular, pcMp^{c} \mid M with MM defined as above.

For each pSp \in \mathcal{S}, let ipi_{p} be such that bip=pepb_{i_{p}} = p^{e_{p}} and choose the smallest nonnegative integer aipa_{i_{p}} satisfying
pepcaip(Mpep)u p^{e_{p}-c} \left\lvert\, a_{i_{p}} \left( \frac{M}{p^{e_{p}}} \right) - u \right.
Such an aipa_{i_{p}} must exist and be at most pepcp^{e_{p}-c}; indeed, Mpep\frac{M}{p^{e_{p}}} is an integer coprime to pp, so we can take aipa_{i_{p}} to be equal to uu times its multiplicative inverse modulo pepcp^{e_{p}-c}.

The sum of the contributions to the sum from the aipa_{i_{p}} is at most
pSpepcpep=pSpc<α \sum_{p \in \mathcal{S}} \frac{p^{e_{p}-c}}{p^{e_{p}}} = \sum_{p \in \mathcal{S}} p^{-c} < \alpha
So, we have
uM=pSaippep+rpSpc, \frac{u}{M} = \sum_{p \in \mathcal{S}} \frac{a_{i_{p}}}{p^{e_{p}}} + \frac{r}{\prod_{p \in \mathcal{S}} p^{c}},
where rr is an integer because of our choice of aipa_{i_{p}} and rr is nonnegative because of the bound on uu. Simply choose ai=ra_{i} = r where bi=pSpcb_{i} = \prod_{p \in \mathcal{S}} p^{c} to complete the proof.

Solution 2

We reduce to the claim as in Solution 1, and provide an alternative approach for constructing the aia_{i}.

Let p0Sp_{0} \in \mathcal{S} be the smallest prime in S\mathcal{S}. Let z0=u/Mz_{0} = u / M. We construct a sequence z0,z1,z2,z_{0}, z_{1}, z_{2}, \ldots and values of aia_{i} by the following iterative process: to construct zj+1z_{j+1},
- select the largest prime pSp \in \mathcal{S} dividing the denominator of zjz_{j}, and let μ\mu be the number of times pp divides the denominator of zjz_{j};
- choose the largest ν\nu such that p0νpμbnp_{0}^{\nu} p^{\mu} \leqslant b_{n}, and let ini \leqslant n be such that bi=p0νpμb_{i} = p_{0}^{\nu} p^{\mu};
- choose 0ai<p0 \leqslant a_{i} < p such that the denominator of zkai/biz_{k} - a_{i} / b_{i} has at most μ1\mu - 1 factors of pp, and let zk+1=zkai/biz_{k+1} = z_{k} - a_{i} / b_{i};
- continue until p0p_{0} is the only prime dividing the denominator of zkz_{k}.

Note that we can always choose aia_{i} in step 3; by construction, zkbiz_{k} b_{i} has no factors of pp in its denominator, so must be realised as an element of Zp\mathbb{Z}_{p}.

Each time we do this, bi>M/p0b_{i} > M / p_{0} by construction, so
aibi<pp0Mp0p1M, \frac{a_{i}}{b_{i}} < \frac{p p_{0}}{M} \leqslant \frac{p_{0} p_{1}}{M},
where p1p_{1} is the largest prime in S\mathcal{S}.
And the number of times we do this operation is at most
pSp>p0epSlog2(M) \sum_{\substack{p \in \mathcal{S} \\ p > p_{0}}} e_{p} \leqslant |\mathcal{S}| \log_{2}(M)
so the sum of the ai/bia_{i} / b_{i} we have assigned is at most Sp0p1log2(M)/M|\mathcal{S}| p_{0} p_{1} \log_{2}(M) / M.

Choose nn large enough that log2(M)/M<α\log_{2}(M) / M < \alpha; after subtracting the above choices of ai/bia_{i} / b_{i} from u/Mu / M, we have a quantity of the form r/p0ep0r / p_{0}^{e_{p_{0}}}, where rr is an integer by construction and rr is positive by the above bounds. Simply set ai=ra_{i} = r where bi=p0eP0b_{i} = p_{0}^{e_{P_{0}}} to complete the proof.

Solution 3

As in Solution 1, we may handle S=1|\mathcal{S}| = 1 and S={2,3}\mathcal{S} = \{2,3\} separately; otherwise, we can define α\alpha as we did in that solution. Also define epe_{p} to be the largest nonnegative integer such that pepbnp^{e_{p}} \leqslant b_{n} as we did in Solution 1.

We will show that, for nn sufficiently large, we may choose some jnj \leqslant n, and positive integers aia_{i}, such that
ijaibiij1bi<α \sum_{i \neq j} \frac{a_{i}}{b_{i}} - \sum_{i \neq j} \frac{1}{b_{i}} < \alpha
and all aibi\frac{a_{i}}{b_{i}} are integer multiples of 1bj\frac{1}{b_{j}}. We then set aja_{j} to be the least positive integer such that the sum on the left is an integer, which will obviously have the required value.

Concretely, choose jj such that bj=pSpep/S]b_{j} = \prod_{p \in \mathcal{S}} p^{\left.e_{p} / |\mathcal{S}| \right]}, which is less than bnb_{n} by construction. For iji \neq j, set ai=bi/gcd(bi,bj)a_{i} = b_{i} / \operatorname{gcd}(b_{i}, b_{j}). We have
ijaibiij1bi<ijai>1aibi \sum_{i \neq j} \frac{a_{i}}{b_{i}} - \sum_{i \neq j} \frac{1}{b_{i}} < \sum_{\substack{i \neq j \\ a_{i} > 1}} \frac{a_{i}}{b_{i}}
If ai>1a_{i} > 1, then there must be some pSp \in \mathcal{S} for which pep/S]+1bip^{\left\lfloor e_{p} / |\mathcal{S}| \right] + 1} \mid b_{i}, and so
aibi=1gcd(bi,bj)1p[ep/S]<pbn1/S \frac{a_{i}}{b_{i}} = \frac{1}{\operatorname{gcd}(b_{i}, b_{j})} \leqslant \frac{1}{p^{\left[e_{p} / |\mathcal{S}| \right]}} < \frac{p}{b_{n}^{1 / |\mathcal{S}|}}
where the last inequality follows from the fact that pep+1>bnp^{e_{p} + 1} > b_{n}.

Now npS(logp(bn)+1)(2logbn)Sn \leqslant \prod_{p \in \mathcal{S}} (\log_{p}(b_{n}) + 1) \leqslant (2 \log b_{n})^{|\mathcal{S}|}, so
ijai>1aibi(2logbn)Sbn1/S \sum_{\substack{i \neq j \\ a_{i} > 1}} \frac{a_{i}}{b_{i}} \leqslant \frac{(2 \log b_{n})^{|\mathcal{S}|}}{b_{n}^{1 / |\mathcal{S}|}}
and so we can choose nn large enough that this quantity is less than α\alpha, as required.

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.