Maths Olympiad Prep

Track / Stage 7 / 118 of 300 #1518 of 1964

Problem 1518

National Olympiad second round; IMO P1/P4
Number theory Difficulty 7.2 Prove it Auswahlwettbewerb zur Internationalen Mathematik-Olympiade · Germany

Let nn be a positive integer and let bb be the largest integer that is smaller than (2833)n(\sqrt[3]{28}-3)^{-n}. Prove that bb cannot be divisible by 6.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Solution:

The complex number ω=1+3i2\omega=\frac{-1+\sqrt{3} i}{2} is, as is well known, a cube root of unity and satisfies ω2=13i2\omega^{2}=\frac{-1-\sqrt{3} i}{2}, ω3=1\omega^{3}=1 and ω2+ω+1=0\omega^{2}+\omega+1=0; in particular
1+ωj+ω2j={3, if j is divisible by three 0 otherwise.  1+\omega^{j}+\omega^{2 j}= \begin{cases}3, & \text{ if } j \text{ is divisible by three } \\ 0 & \text{ otherwise. }\end{cases}
Set rk=283ωk3r_{k}=\sqrt[3]{28} \omega^{k}-3 for k=0,1,2k=0,1,2. By the definition of bb we have r0nb<1\left|r_{0}^{-n}-b\right|<1; since the real parts of ω\omega and ω2\omega^{2} are negative, we have r1>1\left|r_{1}\right|>1 and r2>1\left|r_{2}\right|>1. Thus
b(r0n+r1n+r2n)<br0n+r1n+r2n<3. \left|b-\left(r_{0}^{-n}+r_{1}^{-n}+r_{2}^{-n}\right)\right|<\left|b-r_{0}^{-n}\right|+\left|r_{1}^{-n}\right|+\left|r_{2}^{-n}\right|<3 .
Since (283ωk)3=28\left(\sqrt[3]{28} \omega^{k}\right)^{3}=28, we have
rk1=1283ωk3=(283ωk)333283ωk3=2832ω2k+3283ωk+9 r_{k}^{-1}=\frac{1}{\sqrt[3]{28} \omega^{k}-3}=\frac{\left(\sqrt[3]{28} \omega^{k}\right)^{3}-3^{3}}{\sqrt[3]{28} \omega^{k}-3}=\sqrt[3]{28}^{2} \omega^{2 k}+3 \sqrt[3]{28} \omega^{k}+9
If one raises the polynomial X2+3X+9X^{2}+3 X+9 to the nn-th power, there exist integers c0,,c2nc_{0}, \ldots, c_{2 n} with (X2+3X+9)n=c2nX2n+c2n1X2n1++c0\left(X^{2}+3 X+9\right)^{n}=c_{2 n} X^{2 n}+c_{2 n-1} X^{2 n-1}+\ldots+c_{0}, where c0=9nc_{0}=9^{n} is odd. Substituting X=283ωkX=\sqrt[3]{28} \omega^{k} gives rkn=j=02ncj283jωkjr_{k}^{-n}=\sum_{j=0}^{2 n} c_{j} \sqrt[3]{28}^{j} \omega^{k j}; from this, using (1), we obtain:
r0n+r1n+r2n=j=02ncj283j(1+ωj+ω2j)=302n/3c328 r_{0}^{-n}+r_{1}^{-n}+r_{2}^{-n}=\sum_{j=0}^{2 n} c_{j} \sqrt[3]{28}^{j}\left(1+\omega^{j}+\omega^{2 j}\right)=3 \sum_{0 \leq \ell \leq 2 n / 3} c_{3 \ell} 28^{\ell}
The sum is clearly a multiple of 3 and, moreover, odd, since the summand c328c_{3 \ell} 28^{\ell} is odd for =0\ell=0 and even for >0\ell>0. If bb were divisible by 6, then the absolute value b(r0n+r1n+r2n)\left|b-\left(r_{0}^{-n}+r_{1}^{-n}+r_{2}^{-n}\right)\right| would be at least 3, contradicting (2).

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from de; metadata (topic, difficulty, ordering) added by this project.