Maths Olympiad Prep

Library / /317 of 383

Number theory Difficulty 8.9 Shortlist Prove it IMO

For every real number xx, let x\|x\| denote the distance between xx and the nearest integer. Prove that for every pair (a,b)(a, b) of positive integers there exist an odd prime pp and a positive integer kk satisfying
apk+bpk+a+bpk=1. \left\|\frac{a}{p^{k}}\right\|+\left\|\frac{b}{p^{k}}\right\|+\left\|\frac{a+b}{p^{k}}\right\|=1 .

Solution

Notice first that x+12\left\lfloor x+\frac{1}{2}\right\rfloor is an integer nearest to xx, so x=x+12x\|x\|=\left|\left\lfloor x+\frac{1}{2}\right\rfloor-x\right|. Thus we have
x+12=x±x. \left\lfloor x+\frac{1}{2}\right\rfloor=x \pm\|x\| .
For every rational number rr and every prime number pp, denote by vp(r)v_{p}(r) the exponent of pp in the prime factorisation of rr. Recall the notation (2n1)!!(2n-1)!! for the product of all odd positive integers not exceeding 2n12n-1, i.e., (2n1)!!=13(2n1)(2n-1)!!=1 \cdot 3 \cdots (2n-1).

Lemma. For every positive integer nn and every odd prime pp, we have
vp((2n1)!!)=k=1npk+12. v_{p}((2n-1)!!)=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^{k}}+\frac{1}{2}\right\rfloor .
Proof. For every positive integer kk, let us count the multiples of pkp^{k} among the factors 1,3,,2n11,3, \ldots, 2n-1. If \ell is an arbitrary integer, the number (21)pk(2\ell-1)p^{k} is listed above if and only if
0<(21)pk2n12<npk+121npk+12. 0<(2\ell-1)p^{k} \leqslant 2n \quad \Longleftrightarrow \quad \frac{1}{2}<\ell \leqslant \frac{n}{p^{k}}+\frac{1}{2} \quad \Longleftrightarrow \quad 1 \leqslant \ell \leqslant \left\lfloor\frac{n}{p^{k}}+\frac{1}{2}\right\rfloor .
Hence, the number of multiples of pkp^{k} among the factors is precisely mk=npk+12m_{k}=\left\lfloor\frac{n}{p^{k}}+\frac{1}{2}\right\rfloor. Thus we obtain
vp((2n1)!!)=i=1nvp(2i1)=i=1nk=1vp(2i1)1=k=1=1mk1=k=1npk+12. v_{p}((2n-1)!!)=\sum_{i=1}^{n} v_{p}(2i-1)=\sum_{i=1}^{n} \sum_{k=1}^{v_{p}(2i-1)} 1=\sum_{k=1}^{\infty} \sum_{\ell=1}^{m_{k}} 1=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^{k}}+\frac{1}{2}\right\rfloor .
\square

In order to prove the problem statement, consider the rational number
N=(2a+2b1)!!(2a1)!!(2b1)!!=(2a+1)(2a+3)(2a+2b1)13(2b1). N=\frac{(2a+2b-1)!!}{(2a-1)!!\cdot(2b-1)!!}=\frac{(2a+1)(2a+3) \cdots (2a+2b-1)}{1 \cdot 3 \cdots (2b-1)} .
Obviously, N>1N>1, so there exists a prime pp with vp(N)>0v_{p}(N)>0. Since NN is a fraction of two odd numbers, pp is odd.

By our lemma,
0<vp(N)=k=1(a+bpk+12apk+12bpk+12). 0<v_{p}(N)=\sum_{k=1}^{\infty}\left(\left\lfloor\frac{a+b}{p^{k}}+\frac{1}{2}\right\rfloor-\left\lfloor\frac{a}{p^{k}}+\frac{1}{2}\right\rfloor-\left\lfloor\frac{b}{p^{k}}+\frac{1}{2}\right\rfloor\right) .
Therefore, there exists some positive integer kk such that the integer number
dk=a+bpk+12apk+12bpk+12 d_{k}=\left\lfloor\frac{a+b}{p^{k}}+\frac{1}{2}\right\rfloor-\left\lfloor\frac{a}{p^{k}}+\frac{1}{2}\right\rfloor-\left\lfloor\frac{b}{p^{k}}+\frac{1}{2}\right\rfloor
is positive, so dk1d_{k} \geqslant 1. By the earlier formula we have
1dk=a+bpkapkbpk±a+bpk±apk±bpk=±a+bpk±apk±bpk. 1 \leqslant d_{k}=\frac{a+b}{p^{k}}-\frac{a}{p^{k}}-\frac{b}{p^{k}} \pm \left\|\frac{a+b}{p^{k}}\right\| \pm \left\|\frac{a}{p^{k}}\right\| \pm \left\|\frac{b}{p^{k}}\right\|= \pm \left\|\frac{a+b}{p^{k}}\right\| \pm \left\|\frac{a}{p^{k}}\right\| \pm \left\|\frac{b}{p^{k}}\right\| .
Since x<12\|x\|<\frac{1}{2} for every rational xx with odd denominator, the relation above can only be satisfied if all three signs on the right-hand side are positive and dk=1d_{k}=1. Thus we get
apk+bpk+a+bpk=dk=1 \left\|\frac{a}{p^{k}}\right\|+\left\|\frac{b}{p^{k}}\right\|+\left\|\frac{a+b}{p^{k}}\right\|=d_{k}=1
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 reproduced verbatim; metadata (topic, difficulty) added by this project.