# Fall 2016, problem 23

Show that there are infinitely many positive integers $n$ for which all the prime divisors of $n^{2}+n+1$ are not more then $\sqrt{n}$.

francois
5 years ago

With ${\phi _n}\left( X \right) = \prod\limits_{\scriptstyle0 \le k \le n - 1\atop\scriptstyle\gcd \left( {k,n} \right) = 1}^{} {\left( {X - {e^{\frac{{2ik\pi }}{n}}}} \right)}$

${\phi _n}$ cyclotomic polynomial of order n with integer coefficients and leading term 1.

${X^n} - 1 = \prod\limits_{d\left| n \right.}^{} {{\phi _d}\left( X \right)}$

${X^{3n}} - 1 = \prod\limits_{d\left| {3n} \right.}^{} {{\phi _d}\left( X \right)}$

${X^{2n}} + {X^{n}} + 1 = \prod\limits_{d\left| {3n} \right.,\,d\nmid n}^{} {{\phi _d}\left( X \right)}$

If $3n = {p_1}{p_2}...{p_k}$ with ${p_i}$ prime number of index i

$\left( {{p_1} = 2,\,{p_2} = 3} \right)\,$

with $\varphi \left( n \right)$ Euler Totient of n

${\phi _d}\left( X \right)\mathop \sim \limits_{ + \infty } {X^{\varphi \left( d \right)}}$

If $d = {p_{{i_1}}}...{p_{{i_l}}}$ and $\frac{3n}{d} = {p_{{j_1}}}...{p_{{j_{k - l}}}}$

$\varphi \left( d \right) = d\left( {1 - \frac{1}{{{p_{{i_1}}}}}} \right)...\left( {1 - \frac{1}{{{p_{{i_l}}}}}} \right)$

$\frac{{\varphi \left( d \right)}}{n} = \frac{3}{{{p_{{j_1}}}...{p_{{j_{k - l}}}}}}\left( {1 - \frac{1}{{{p_{{i_1}}}}}} \right)...\left( {1 - \frac{1}{{{p_{{i_l}}}}}} \right) \le 3\left( {1 - \frac{1}{{{p_1}}}} \right)...\left( {1 - \frac{1}{{{p_k}}}} \right)$

$\left( {\frac{1}{{{p_{{j_m}}}}} \le 1 - \frac{1}{{{p_{{j_m}}}}}} \right)$

If $\left( {1 - \frac{1}{{{p_1}}}} \right)...\left( {1 - \frac{1}{{{p_k}}}} \right)$ < $\frac{1}{6}$

When $X \to + \infty$ all the factors ${\phi _d}\left( X \right)$ verify ${\phi _d}\left( X \right) \ll \sqrt {{X^n}} = {X^{\frac{n}{2}}}$

As $\mathop {\lim }\limits_{k \to + \infty } \left( {1 - \frac{1}{{{p_1}}}} \right)...\left( {1 - \frac{1}{{{p_k}}}} \right) = 0$

( $\sum\limits_k^{} {\frac{1}{{{p_k}}}} = + \infty$ )

we can find k vérifying $\left( {1 - \frac{1}{{{p_1}}}} \right)...\left( {1 - \frac{1}{{{p_k}}}} \right)$ < $\frac{1}{6}$

All the prime factors of ${X^{2n}} + {X^{n}+1}$ which are prime factors of the ${\phi _d}\left( X \right)$ are less than $\sqrt {{X^n}}$ for X sufficiently great (with X integer).

As

$\left( {1 - \frac{1}{2}} \right)\left( {1 - \frac{1}{3}} \right)\left( {1 - \frac{1}{5}} \right)\left( {1 - \frac{1}{7}} \right)\left( {1 - \frac{1}{{11}}} \right)\left( {1 - \frac{1}{{13}}} \right)\left( {1 - \frac{1}{{17}}} \right)\left( {1 - \frac{1}{{19}}} \right)\left( {1 - \frac{1}{{23}}} \right) = \frac{{{\rm{110592}}}}{{{\rm{676039}}}}$ < $\frac{1}{6}$

we can take

$n = 2 \times 5 \times 7 \times ... \times 23 = {\rm{74364290}}$

For N sufficiently great all the prime factors of ${m^2} + m + 1$ wiith $m = {N^{{\rm{74364290}}}}$ are less than $\sqrt m$