Maths Olympiad Prep

Library / /1 of 4

Number theory Difficulty 8.3 Shortlist Prove it Taiwan

For positive integers nn and k2k \ge 2 define Ek(n)E_k(n) as the greatest exponent rr such that krk^r divides n!n!. Prove that there are infinitely many nn such that E10(n)>E9(n)E_{10}(n) > E_9(n) and infinitely many mm such that E10(m)<E9(m)E_{10}(m) < E_9(m).

Solution

Set n=52l1n = 5^{2l-1}, we have
E10(n)=v5(n!)=52l2+52l3++5+1=52l114=n14. E_{10}(n) = v_5(n!) = 5^{2l-2} + 5^{2l-3} + \dots + 5 + 1 = \frac{5^{2l-1}-1}{4} = \frac{n-1}{4}.
Since n2(mod4)n \equiv 2 \pmod 4, so
E9(n)=12v3(n!)<12(n23+n32+)=n413. E_9(n) = \frac{1}{2}v_3(n!) < \frac{1}{2}\left(\frac{n-2}{3} + \frac{n}{3^2} + \dots\right) = \frac{n}{4} - \frac{1}{3}.
Thus E9(n)<E10(n)E_9(n) < E_{10}(n).

Similarly, set m=34l2m = 3^{4l-2}. Then we have
E9(m)=12v3(m!)=m14 E_9(m) = \frac{1}{2}v_3(m!) = \frac{m-1}{4}
and since m4(mod5)m \equiv 4 \pmod 5,
E10(m)<m45+m52+=m445. E_{10}(m) < \frac{m-4}{5} + \frac{m}{5^2} + \dots = \frac{m}{4} - \frac{4}{5}.
We have E10(m)<E9(m)E_{10}(m) < E_9(m)

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 translated into English from en; metadata (topic, difficulty) added by this project.