38

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$

I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid n!$.

Alternatively, I considered the Pell equation $n^2+1=5m^2$, $2m<n$, but for $2015$ I can't figure it out.

Jyrki Lahtonen
  • 133,153
  • A first (ridiculously trivial) comment: there is nothing really special about $2015$, so the very same approach should either work for any integer $k$ ($n^k+1\mid n!$ for infinitely many $n$) or any odd integer $2k+1$ ($n^{2k+1}+1\mid n!$ for infinitely many $n$). – Clement C. Jul 18 '15 at 18:01
  • 1
    My heuristic thoughts is that for any arbitrary integer $m>0$ and all sufficiently large $n$ then $n!$ is bounded below by an increasing monic polynomial in $n$ of degree $m$. You just have to argue that any sufficiently large asymptotic difference over $n^{k}+1$ (aka $m-k$) implies the divisibility. – zibadawa timmy Jul 18 '15 at 18:03
  • 1
    Also sprach Mathematica: If we replace 2015 with a modest exponent like 3, there are 1738 solutions with $n\le10000$ (surprisingly many IMHO). With 5 in place of 2015 it found two solutions $n=984$ and $n=1753$ with $n<2000$ and a total of 14 solutions below 10000. With exponent 7 no solutions below 20000. – Jyrki Lahtonen Jul 18 '15 at 18:20
  • 6
    Can you shed a bit of light to the origin of this question? First it looked like a contest problem. Now it is a conjecture. Can you give any kind of evidence supporting this conjecture? The use of Pell equation is very nice, but nothing similar exists for higher exponents. No equation of the form $n^3+1=C m^3$ has infinitely many solutions, because those are elliptic curves, and they are known to have only fnitely many integer points. The same holds for higher exponents (Faltings). Mind you, it still looks like there probably are infinitely many solutions with exponent 3. – Jyrki Lahtonen Jul 18 '15 at 18:27
  • @JyrkiLahtonen, I would add that one ought to try $n^3 + 1$ dividing $n!,$ maybe $n^5+1,$ as well as finding the source of this and the relevant background of the person posting. I see, you edited before I refreshed screen... – Will Jagy Jul 18 '15 at 18:36
  • 2
    @Will: My sentiment exactly. The OP has a long history of posting contest problems, and 2015 pointed in that direction. I hope to hear more, but I think that proving this for exponent 5 would already be non-trivial (more optimistic about 3 actually). – Jyrki Lahtonen Jul 18 '15 at 18:38
  • With exponent 3 we have 4634 solutions up to n=25000. If anything it looks like the density may be going up as we increase the range. I don't have any kind of intuition about this. More or less we are looking for integers $n$ such that all the prime factors of $n^3+1$ are less than $n$ (it is then highly probable that the number divides $n!$). I guess it should not be surprising that there are plenty of those. It's all about factoring $n^2-n+1$. – Jyrki Lahtonen Jul 18 '15 at 18:44
  • 1
    @Jyrki, not necessarily on any website, I guarantee there is literature about, say, the probability, for fixed $k,$ that some large number $m$ has all prime factors below $m^{1/k}$ – Will Jagy Jul 18 '15 at 18:48
  • 2
    No positive solutions for $n\le10^5$. – Lucian Jul 18 '15 at 20:24

3 Answers3

14

Modest progress. There are infinitely many integers $n$ such that $n^3+1\mid n!$.

We always have $n^3+1=(n+1)(n^2-n+1)$. Let $n=k^2+1$. Then $$ n^2-n+1=(1+k+k^2)(1-k+k^2). $$ Assume further that $k\equiv1\pmod3$. In that case $1+k+k^2$ and $n+1=2+k^2$ are both divisible by $3$. For all sufficiently large $k\equiv1\pmod3$ we thus have $$ (k^2+1)^3+1=3^2\cdot\frac{k^2+2}3\cdot\frac{k^2+k+1}3(k^2-k+1) $$ that is clearly a factor of $(k^2+1)!$.

Jyrki Lahtonen
  • 133,153
  • Posting this because it may generalize to other small exponents. – Jyrki Lahtonen Jul 18 '15 at 19:07
  • 1
    Does not directly help, but a book Prime Numbers and Computer Methods for Factorization, second edition, by Hans Riesel, on page 162 quotes Knuth and Trabb-Pardo (1976), the proportion of numbers $n$ with largest prime factor no bigger than $n^{1/\alpha}$ is given by an alternating series involving polylogarithm functions; table and graph on page 163 – Will Jagy Jul 18 '15 at 20:46
  • It's nice,Thank you,but How to solve $2015?$ –  Jul 19 '15 at 04:15
  • 3
    For the $5$ and $7$ cases (7 is not needed here, though), the following identities may be useful: $$\frac{x^5+1}{x+1} = (x^2+3x+1)^2-5x(x+1)^2,$$ $$\frac{x^7+1}{x+1} = (x+1)^6 - 7x(x^2+x+1)^2.$$ In particular if $x$ has a suitable form then these are differences of squares, and so can be factored. – zibadawa timmy Jul 19 '15 at 20:23
  • Going further on that: by equation (6) here, for $x=mk^2$ we can always write $(x^m+1)/(x+1)$ as a difference of squares for suitable $m$ (squarefree seems to suffice). It even provides an explicit definition for the two polynomials, though they are not obviously polynomials. – zibadawa timmy Jul 19 '15 at 21:47
  • Thanks, @zibadawatimmy. Yesterday I checked out my usual sources on Aurifeuillian stuff WP and Paul Garrett's notes. I didn't feel particularly enlightened, but I didn't try very hard. Of course, the numerical testing revealed that for higher $m$ we cannot expect to use a low degree polynomial of $k$ in place of $n$. Your observations might serve as the first substitution. Then we need another to factor it further. – Jyrki Lahtonen Jul 19 '15 at 22:10
  • 1
    Rats. @zibadawatimmy: That expansion is for $(x^5-1)/(x-1)$. We can, of course, write $-x$ in place of $x$, but then it becomes a sum of two squares when $x=5n^2$ :-( – Jyrki Lahtonen Jul 22 '15 at 10:20
  • @JyrkiLahtonen Oops, you're right. Equation (6) that I linked in the comment after that would imply you can get it as a difference of squares, but either there's an error in that equation or I'm too dumb to do it correctly right now as it's not working out for me. – zibadawa timmy Jul 22 '15 at 17:23
13

It suffices to show that for infinitely many $n$, the largest prime factor of $n^{2015}+1$ is at most $\sqrt{n}$. Indeed, if $n$ is such a large integer and $p$ is a prime, then the largest value of $a$ for which $p^a\mid n^{2015}+1$ is $\leq c \log n$ for some constant $c$, while $n!$ is divisible by $p^a$ with $a\geq \frac{n}{p}-1\geq \sqrt{n}-1>c \log n$. It was shown by Schinzel (Theorem 13 in https://eudml.org/doc/204826) that for any nonzero integers $A$ and $B$, any integer $k\geq 2$ and any $\varepsilon>0$ there exist infinitely many integers $n$ such that the largest prime factor of $An^k+B$ is less than $n^{\varepsilon}$. In particular, the claim of the problem holds with $2015$ replaced by any positive integer.

dejongbrent
  • 354
Joni Teräväinen
  • 676
4

Since $2015 = 5\cdot 13\cdot 31 $, and $n^a + 1| n^{ab}+1 $ if $b$ is odd, a necessary condition for $n^{2015}+1 | n! $ is $n^m+1 | n!$ for every $m$ in $\{5, 13, 31 , 5\cdot 13 , 5\cdot 31 , 13\cdot 31 \} $.

Solutions are going to be hard to find. All those expressions of the form $n^j-n^{j-1}+...-n+1 $ for odd $j$ will have to have all prime factors $\le n$ in order to divide $n!$.

marty cohen
  • 107,799