# Is there a polynomial such that $F(p)$ is always divisible by a prime greater than $p$?

Is there an integer-valued polynomial $F$ such that for all prime $p$, $F(p)$ is divisible by a prime greater than $p$? For example, $n^2+1$ doesn't work, since $7^2+1 = 2 \cdot 5^2$. I can see that without loss of generality it can be assumed that $F(0) \ne 0$. Also, it is enough to find a polynomial where the property is true for sufficiently large prime $p$, since we could multiply that polynomial by some prime in the sufficiently large range and fix all the smaller cases.

I think it is possible that there are no such polynomials, is there any good hint for proving this?

I can't find any solutions to $\text{gpf}(p^4+1) \le p$ for prime $p \le 10000$, where $\text{gpf}$ is the greatest prime factor, but there are plenty for $\text{gpf}(p^3+1) \le p$, for example $\text{gpf}(2971^3+1) = 743 \lt 2971$. So I guess $F(p) = p^4+1$ might be an example. I also checked higher powers for small $p$ and couldn't find solutions there either, so $k \ge 4 \rightarrow \text{gpf}(p^k+1) \gt p$ is plausible.

• Is there...? - No, there isn't. – Lucian Feb 5 '16 at 14:54
• Now it seems like the number of $p$-smooth numbers less than $F(p)$ is bounded below by $F(p)$ times a constant (the value of the Dickman function), so heuristically there should always be an infinite number of $p$-smooth values. The constant shrinks very quickly which is consistent with $p^4+1$ having such a large counterexample. – Dan Brumleve Feb 5 '16 at 17:00

$$10181^4 + 1 = 2 \cdot 17 \cdot 1657 \cdot 4657 \cdot 5113 \cdot 8009$$

I have many factoring variants. Many of the commands in the following involve string variables, these are used in the versions where the factorization will actually be printed out, but are irrelevant here.

part of file form.h

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <sstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <gmp.h>
#include <gmpxx.h>
using namespace std;

int  mp_all_prime_factors_below_bound( mpz_class  i, mpz_class bound)
{
int squarefac = 0;
string fac;
fac = " = ";
mpz_class p = 2;
mpz_class  temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}

if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p <= bound && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " cdot ";
//  fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
if (p >2) ++squarefac ;
}
}  // if p is factor
++p;
// cerr << " temp " << temp << endl;
} // while p
if (temp > 1 && primefac >= 1) fac += " ";
if (temp > 1 && temp < bound * bound  ){ fac += " cdot "; fac +=   temp.get_str()   ;}

if (temp > 1 && temp >= bound * bound  ){ fac += " cdot mbox{BIG} "; }
//  if (squarefac) fac += "      WOW " ;
} // temp > 1
// cerr << " temp " << temp << endl;
return ( temp  <= bound ) ;
} // mp_all_prime_factors_below_bound

• How did you get this? 0.0 – Martijn Feb 20 '16 at 18:36
• @Martijn, programs I write in C++ with GMP. Many variants of factoring by trial division up to a bound, so factor_to_bound( int n, int bound) reports whether a complete factorization occurs with trial division by numbers from 2 to bound. It stays fast because it quits if an overly large factor is left over, just ignores that. Here I took bound = n + 1000. Note that I tried polynomial $p^8 + 1,$ no luck so far. – Will Jagy Feb 20 '16 at 19:02
• You have that source code published somewhere? – Martijn Feb 20 '16 at 19:04
• @Martijn, edited in the relevant command, from a file I call form.h which would then be included in some .cc program. – Will Jagy Feb 20 '16 at 19:18
• Awesome! Looks great. – Martijn Feb 20 '16 at 22:04

Probably not, but this might be very hard to prove. For each $\epsilon > 0$ the asymptotic fraction of integers $x<N$ that are multiples of primes $<x^\epsilon$ (a.k.a. "$x^\epsilon$-smooth") is positive, though it decays rapidly with $\epsilon$. (See for instance this Wikipedia page.) So it reasonable to expect that for any polynomial $F$ a positive fraction of primes $p$ will have $F(p)$ a product of primes less than $p$ (choose any positive $\epsilon < 1 \,/ \deg F$).

[Added a minute later: I see that Dan Brumleve said much the same in a comment on the original question, referring instead to the Wikipedia page on the Dickman function.]