Maths Olympiad Prep

Library / /38 of 155

Number theory Difficulty 5.4 AIME, harder Prove it Saudi Arabia

Prove that there are infinitely many positive integer nn such that n!n! is divisible by n31n^{3}-1.

Solution

We have n31=(n1)(n2+n+1)n^{3}-1=(n-1)\left(n^{2}+n+1\right). We shall prove that there are infinitely many positive integers nn such that n2+n+1n^{2}+n+1 can be represented as the product of some factors less than n1n-1 and then deduce that n31n^{3}-1 divides n!n!. In fact, we first choose n=m2n=m^{2} for some positive integer mm, one has
n2+n+1=m4+m2+1=(m2+1)2m2=(m2m+1)(m2+m+1). n^{2}+n+1=m^{4}+m^{2}+1=\left(m^{2}+1\right)^{2}-m^{2}=\left(m^{2}-m+1\right)\left(m^{2}+m+1\right) .
Next, we choose m=3k+1m=3k+1, then
m2+m+1=(3k+1)2+(3k+1)+1=9k2+6k+1+3k+1+1=3(3k2+3k+1)m^{2}+m+1=(3k+1)^{2}+(3k+1)+1=9k^{2}+6k+1+3k+1+1=3\left(3k^{2}+3k+1\right)
and
m2m+1=(3k+1)2(3k+1)+1=9k2+6k+13k1+1=9k2+3k+1m^{2}-m+1=(3k+1)^{2}-(3k+1)+1=9k^{2}+6k+1-3k-1+1=9k^{2}+3k+1.
It is clear that
3<3k2+3k+1<9k2+3k+1<9k2+6k=(3k+1)21=n1. 3<3k^{2}+3k+1<9k^{2}+3k+1<9k^{2}+6k=(3k+1)^{2}-1=n-1 .
Therefore, for n=(3k+1)2n=(3k+1)^{2} with any positive integer kk, it follows that n!n! is divisible by
3(3k2+3k+1)(9k2+3k+1)(9k2+6k)=n31. 3\left(3k^{2}+3k+1\right)\left(9k^{2}+3k+1\right)\left(9k^{2}+6k\right)=n^{3}-1 .
The problem is proved. \square

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.