37
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – zibadawa timmy Jul 18 '15 at 18:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 18 '15 at 18:20
  • 6
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 18 '15 at 18:27
  • 2
    $\begingroup$ @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). $\endgroup$ – Jyrki Lahtonen Jul 18 '15 at 18:38
  • 2
    $\begingroup$ No positive solutions for $n\le10^5$. $\endgroup$ – Lucian Jul 18 '15 at 20:24
14
$\begingroup$

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)!$.

$\endgroup$
  • $\begingroup$ Posting this because it may generalize to other small exponents. $\endgroup$ – Jyrki Lahtonen Jul 18 '15 at 19:07
  • 1
    $\begingroup$ 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 $\endgroup$ – Will Jagy Jul 18 '15 at 20:46
  • $\begingroup$ It's nice,Thank you,but How to solve $2015?$ $\endgroup$ – user225250 Jul 19 '15 at 4:15
  • 3
    $\begingroup$ 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. $\endgroup$ – zibadawa timmy Jul 19 '15 at 20:23
  • 1
    $\begingroup$ 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$ :-( $\endgroup$ – Jyrki Lahtonen Jul 22 '15 at 10:20
12
+200
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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!$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy