Maths Olympiad Prep

Library / /26 of 50

Number theory Difficulty 7.8 National Olympiad, round 2 Prove it Turkey

Find the largest positive integer nn which is divisible by all positive integers whose cube is not greater than nn.

Solution

The answer is 420420.

Let us consider the positive integer mm so that m3≤n<(m+1)3m^3 \leq n < (m+1)^3. As n=420n = 420 satisfies the conditions, we will consider the case when m≥7m \geq 7. Note that each of mm, m−1m-1, m−2m-2 and m−3m-3 divides nn and hence lcm⁡(m,m−1,m−2,m−3)\operatorname{lcm}(m, m-1, m-2, m-3) divides nn. Since gcd⁡(n−1,n−2)=1\gcd(n-1, n-2) = 1, gcd⁡(n,n−3)\gcd(n, n-3) divides 33 and gcd⁡(n(n−3),(n−1)(n−2))\gcd(n(n-3), (n-1)(n-2)) divides 22, we have that

m(m−1)(m−2)(m−3)6 \frac{m(m-1)(m-2)(m-3)}{6}
divides nn. Therefore,
m(m−1)(m−2)(m−3)6<(m+1)3 \frac{m(m-1)(m-2)(m-3)}{6} < (m+1)^3
and hence m≤12m \leq 12.

If m=11m = 11 or 1212, then 11⋅7⋅5⋅9⋅8=27720∣n11 \cdot 7 \cdot 5 \cdot 9 \cdot 8 = 27720 \mid n, but 133=2197<2772013^3 = 2197 < 27720.

If m=9m = 9 or 1010, then 7⋅5⋅9⋅8=2520∣n7 \cdot 5 \cdot 9 \cdot 8 = 2520 \mid n, but 113=1331<252011^3 = 1331 < 2520.

If m=8m = 8, then 7⋅5⋅3⋅8=840∣n7 \cdot 5 \cdot 3 \cdot 8 = 840 \mid n, but 93=729<8409^3 = 729 < 840.

If m=7m = 7, then 7⋅5⋅3⋅4=420∣n7 \cdot 5 \cdot 3 \cdot 4 = 420 \mid n and n<83=512n < 8^3 = 512. Therefore n=420n = 420.

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.