Let us restate the problem as showing that there are infinitely many primes
such that there exists some positive integer
with
and
.
We know that
is a square mod
if
, and we know that there are infinitely many primes
. Now, there is some
such that
. However, if
, then we also have
. Therefore, we can pick such an
that is less than
. We are almost done, since we have now found such an
with
. We just now need to get the
.
We will show that we can't have
be too close to
. Say
where
is odd. Then, say we had
, so
![\[4^{-1}(p^2-2pk+k^2)\equiv -1\pmod{p}\]](//latex.artofproblemsolving.com/7/8/f/78f6dbe9ec106771cfa3e3ac5395187aa986170b.png)
or
![\[k^2\equiv p-4\pmod{p}.\]](//latex.artofproblemsolving.com/4/c/5/4c58ad102d0ea6f68643388b0bb3448f577f02c7.png)
If we choose
, we can make sure this doesn't happen. Thus, any solution
must be less than
. Stated again, we can pick some
such that
. We will show this is enough to finish the problem. Note that
However, the second possibility violates
, so we must have that
![\[p>\frac{(4n+1)+\sqrt{8n-15}}{2}=2n+1/2+\sqrt{2n-15/4}\]](//latex.artofproblemsolving.com/5/9/c/59c5b933daed24ecd214090de8520fb8c0acaa8f.png)
which for large enough
and
imply that
![\[p>2n+\sqrt{2n}.\]](//latex.artofproblemsolving.com/7/f/8/7f8a516a8ff5c7e784edd72e0af37f01f7207ba2.png)
Thus, we have shown that we can always pick
and
arbitrarily large so that
and
.
by yayups, Jun 29, 2017, 5:14 AM 
such that 
has a prime divisor greater than 
.
April 2021
September 2020
such that there exists some positive integer 
and 
.
is a square mod 
,
.
.
.
.
where 
is odd. Then, say we had ![\[4^{-1}(p^2-2pk+k^2)\equiv -1\pmod{p}\]](http://latex.artofproblemsolving.com/7/8/f/78f6dbe9ec106771cfa3e3ac5395187aa986170b.png)
or![\[k^2\equiv p-4\pmod{p}.\]](http://latex.artofproblemsolving.com/4/c/5/4c58ad102d0ea6f68643388b0bb3448f577f02c7.png)
If we choose 
,
.
such that 
.
However, the second possibility violates 
,![\[p>\frac{(4n+1)+\sqrt{8n-15}}{2}=2n+1/2+\sqrt{2n-15/4}\]](http://latex.artofproblemsolving.com/5/9/c/59c5b933daed24ecd214090de8520fb8c0acaa8f.png)
which for large enough ![\[p>2n+\sqrt{2n}.\]](http://latex.artofproblemsolving.com/7/f/8/7f8a516a8ff5c7e784edd72e0af37f01f7207ba2.png)
Thus, we have shown that we can always pick 