Number theoryDifficulty 5.4AIME, harderProve itSaudi Arabia
Prove that there are infinitely many positive integer n such that n! is divisible by n3−1.
Solution
We have n3−1=(n−1)(n2+n+1). We shall prove that there are infinitely many positive integers n such that n2+n+1 can be represented as the product of some factors less than n−1 and then deduce that n3−1 divides n!. In fact, we first choose n=m2 for some positive integer m, one has n2+n+1=m4+m2+1=(m2+1)2−m2=(m2−m+1)(m2+m+1). Next, we choose m=3k+1, then m2+m+1=(3k+1)2+(3k+1)+1=9k2+6k+1+3k+1+1=3(3k2+3k+1) and m2−m+1=(3k+1)2−(3k+1)+1=9k2+6k+1−3k−1+1=9k2+3k+1. It is clear that 3<3k2+3k+1<9k2+3k+1<9k2+6k=(3k+1)2−1=n−1. Therefore, for n=(3k+1)2 with any positive integer k, it follows that n! is divisible by 3(3k2+3k+1)(9k2+3k+1)(9k2+6k)=n3−1. The problem is proved. □
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.