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.

  • $\begingroup$ 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.. $\endgroup$ – Paolo Leonetti Jan 12 '18 at 22:16
  • $\begingroup$ 1020752329 can be further factored as 2879 $\times$ 354551 $\endgroup$ – 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.

  • $\begingroup$ However, if "smaller" was intended as "smaller than or equal to", then it follows that $n$ is prime. $\endgroup$ – Daniel Fischer Jan 12 '18 at 22:28
  • $\begingroup$ I found some of those examples when I was testing myself. I think I misunderstood the problem should the interval be closed then and not open? $\endgroup$ – Justin Stevenson Jan 12 '18 at 22:45
  • $\begingroup$ I don't know.... $\endgroup$ – B. Goddard Jan 12 '18 at 22:51
  • $\begingroup$ Yeah I'm unsure. if it truly is closed then you're correct its quite easy to find one, however finding one that isn't on the boundary is extremely hard which is why I suspected it's either an extremely large number or the statement is true. $\endgroup$ – Justin Stevenson Jan 12 '18 at 22:53
  • $\begingroup$ @JustinStevenson where did you get the problem? $\endgroup$ – Will Jagy Jan 12 '18 at 23:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.