# Is this number prime?

Prove of disprove the following: If $m,n$ are positive integers, where $n=m^2+m+1$, and $n$ has no prime divisors smaller than $m+1-\sqrt{m}$, then $n$ is prime.

I've been playing around with this problem for quite some time now. I'm convinced there is a very large counterexample. A basic number theory fact is that if a number $n$ has no prime divisors smaller than $\sqrt{n}$ then it must be prime. For this problem $\sqrt{n}=\sqrt{m^2+m+1}$. Now there is a gap between $m+1-\sqrt{m}$ and $\sqrt{m^2+m+1}$ which is small for small $m$ but becomes larger for bigger $m$. This is why I believe there is a large counter example. Therefore, I need to find primes $x_1,x_2, \cdots x_n \in \mathbb{N}$ such that $$\prod_{i=1}^n x_i=m^2+m+1$$ for some $m \in \mathbb{N}$ and, $$x_i \in (m+1-\sqrt{m} , \sqrt{m^2+m+1})$$

Or I need to prove that no such numbers can exist in which I am unsure how to proceed.

Any help or suggestions are appreciated, thanks!

EDIT: I've consulted with my professor while he would not give any hints he did confirm that the interval should in fact be an open interval.

• I suspect too a large example exists: if $m=4^{15}-1$ then $$m^2+m+1=1020752329 \times 1129482119.$$ This is near the bound you are asking here.. – Paolo Leonetti Jan 12 '18 at 22:16
• 1020752329 can be further factored as 2879 $\times$ 354551 – Justin Stevenson Jan 12 '18 at 22:22

If you let $m=a^2$ then $n = (m+1)^2 - m = (a^2+1)^2 - a^2 = (a^2-a+1)(a^2+a+1).$
There are lots of choices for $a$ which make these last two factors simultaneously prime. E.g., $a= 2, 3, 6, 15, 21, \ldots.$ Both factors are in your range, if the range is a closed interval. For $a=6$, $m=36$ and $n=31\cdot 43.$ The factor $31$ is right on the boundary of your interval.
• However, if "smaller" was intended as "smaller than or equal to", then it follows that $n$ is prime. – Daniel Fischer Jan 12 '18 at 22:28