Are there infinitely many pairs $(p,q)\in\mathbb{P}^2$ such that $p>q$ and $p\mid q^2+1$?

This is a very interesting. There are many methods for bounding the greatest prime factor of $n^2+1$, but when $n$ is a prime this gets tricky.

Full disclosure: This was originally posted on AoPS. Here are some arguments for the existance of such solutions: (credit goes to Tintarn)

A standard probabilistic heuristic would indicate that we certainly expect infinitely many such solutions, in fact there should be roughly $\asymp \frac{x}{(\log x)^2}$ solutions with $p,q \le x$. But proving this is of course a completely different matter, and I don't see an easy way to do this. This might just be an extremely hard problem, compared with the famously unsolved problem whether $n^2+1$ is infinitely often prime.

Any ideas, resources or implications are greately appreciated! For more information about the greatest prime factor of $n^2+1$ read these:


1 Answer 1


A sufficient condition is that there are infinite many positive integers $\ k\ $ such that both $$10k+7$$ and $$10k^2+14k+5$$ are prime. This is a consequence of the generalized Bunyakovsky conjecture , which is however open. If we assume this conjecture to be true , because of $$(10k+7)^2+1=2\cdot 5\cdot (10k^2+14k+5)$$ we only have to set $$q:=10k+7$$ $$p:=10k^2+14k+5$$ to get a solution for every suitable $\ k\ $ , hence infinite many pairs doing the job. This is only one of many possible parametrizations we can establish. If any of them has infinite many solutions, infinite many pairs with the desired properties exist. So, the answer to the question should be "yes" although this is of course not a rigorous proof.

  • $\begingroup$ Well, if we allow ourselves the luxury of citing these general conjectures, then we can do with much less work: From Schinzel's Hypothesis H (I suppose this is what you mean by the "generalized Bunyakovsky conjecture") it certainly follows that $\frac{p^2+1}{2}$ is prime for infinitely many primes $p$. $\endgroup$
    – Tintarn
    Jan 22, 2021 at 9:02
  • $\begingroup$ So I agree, we certainly expect this to be true, but the interesting question really is: Can we prove this (which is much weaker than all these general conjectures) unconditionally? $\endgroup$
    – Tintarn
    Jan 22, 2021 at 9:03
  • $\begingroup$ @Tintarn Yes, this is the proper name, but I always think of Bunyakovsky in this context. And yes, the conjecture is much weaker, but I have nevertheless no idea for a proof. $\endgroup$
    – Peter
    Jan 22, 2021 at 9:06

Your Answer

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