Prove that there are infinitely many positive integer $n$ such that $n!$ is divisible by $n^3 -1$.
Problem
Source: 2017 Saudi Arabia Mock BMO I p1
Tags: number theory, divides, divisible, factorial
24.04.2021 00:30
any ideas?
25.04.2021 15:29
All I can think of is $x^3-1=(x-1)(x^2+x+1)$
03.05.2021 14:17
If we let $n=m^2,$ then $$n^3-1=m^6-1=(m+1)(m^2-m+1)(m-1)(m^2+m+1)$$and we want to ensure that $m^2+m+1$ is not prime$.$ We can make it divisible by $3$ by letting $m=3k+1,$ from which we obtain $$n^3-1=m^6-1=(3k+2)(3k)(9k^2+3k+1)(9k^2+9k+3)=3(3k+2)(3k)(9k^2+3k+1)(3k^2+3k+1)$$ Note that all of the factors in the brackets are strictly less than $n=9k^2+6k+1$ and we only need to ensure that they are not equal$.$ But for large $k,$ it is obvious that the numbers $3, 3k+2, 3k, 9k^2+3k+1$ and $3k^2+3k+1$ are distinct$,$ since setting two of them equal would result in a fixed value of $k,$ therefore all of them are distinct positive divisors of $n!$ and we are done$.$
21.09.2021 17:12
oh wow. I hope it's not a fake solve. Let $n=k^2=l^4$ and $3|l.$ Also, we use the algebraic formula, $$x^4+x^2+1= (x^2-x+1)(x^2+x+1).$$So we get $$n^3-1=(k+1)(k-1)(k^2+k+1)(k^2-k+1)$$ Now we have for sufficiently large $n=k^2$ we get $k+1,k-1,k^2-k+1<n=k^2.$ So we just care about $k^2+k+1.$ Firstly we have to take care about the gcds. So we have three conditions to see. Note that $$\gcd(k-1,k^2+k+1)=\gcd(k^2-2k+1,k^2+k+1)=\gcd(3k,k-1) =1,3 $$but we have $$3|k\implies \gcd(3k,k-1) =1.$$ Note that $$\gcd(k+1,k^2+k+1)=\gcd(k+1,k)=1.$$ Note that $$\gcd(k^2+k+1,k^2-k+1)=(k^2+k+1,2k)=1.$$as $k^2+k$ is even and $k^2+k+1$ not divisible by $k.$ So we have no common gcds, which is great! Now let's see the factorization of $$k^2+k+1=l^4+l^2+1=(l^2+l+1)(l^2-l+1).$$As $$\gcd(k^2+k+1,x)=1\implies \gcd(l^2+l+1, x)=1, \gcd(l^2-l+1, x)=1$$where $x\in\{k+1, k-1, k^2+k+1\}.$ Now, note that $l^2+l+1\le l^3-1<l^4=n$ and $l^2-l+1\le l^3+1<l^4=n.$ So we get that $k^2+k+1|n.$ So we get $$ (k+1)(k-1)(k^2+k+1)(k^2-k+1)|n!$$