Let p be a prime of the form p = a^2 + k^n = b^2 + k^m
where (a,b,k,m,n) are positive integers with a > b.
Let S(k) be the set {(k + 1)/4, (k + 1)/5, (k + 7)/16}.

Theorem:
********
No element of S(k) is integral, k is not a square, m - n is odd.

Conjecture:
***********
If k is a non-square positive integer such that no element of S(k)
is integral, then there is an infinitude of primes of the form
p = a^2 + k^n = b^2 + k^m
where (a,b,m,n) are positive integers, a > b, m - n is odd.

Proof of the theorem:
*********************

First, we show that m - n is odd.
Suppose, on the contrary, that m - n = 2*e. Then
(a - b)*(a + b) = k^n*(k^e - 1)*(k^e + 1)
and hence
a - b = F1*F2*F3
a + b = G1*G2*G3
where (F1,F2,F3,G1,G2,G3) are positive integers, with
F1*G1 = k^n
F2*G2 = k^e - 1
F3*G3 = k^e + 1.
Solving for a, we find that
4*p = (2*a)^2 + 4*k^n = (F1*F2*F3 + G1*G2*G3)^2 + 4*F1*G1.
On the right, we replace 4 by
2^2 = (F3*G3 - F2*G2)^2
and obtain the non-trivial factorization
4*p = H1*H2
where
H1 = F1*F3^2 + G1*G2^2
H2 = F1*F2^2 + G1*G3^2.
When k is even, (F2,F3,G2,G3) are odd, with min(F3,G3) > 2,
and at least one of (F1,G1) is even.
Hence each of (F1,G1) must be even, to ensure that H1*H2 is even.
But then each of (H1,H2) is an even integer greater than 2.
But then p = H1*H2/4 > 2 cannot be prime, contra hyp.
When k > 1 is odd, (F1,G1) are odd, with max(F1,G1) > 2.
Hence min(H1,H2) > 3 and p = H1*H2/4 cannot be prime unless
min(H1,H2) = 4. But that is possible only when k = 3, n = 1,
and one of the pairs (F3,G2) and (F2,G3) is (1,1), in which case
p = 3*(3^e +/- 1)^2 + (3^e -/+ 1)^2 = 0 mod 4
cannot be prime, contra hyp. Hence m - n is odd.

Next, we prove that k cannot be a square.
Suppose, on the contrary, that k = K^2. Then
p = a^2 + K^(2*n) = b^2 + K^(2*m).
and each of the exponents (2*n,2*m) is even,
in contradiction to the above result that
their difference must be odd.

Next, we prove that (k + 1)/4 cannot be an integer.
Suppose, on the contrary, that k = -1 mod 4. Then
(a - b)*(a + b) = k^m - k^n = 2 mod 4,
since m and n have opposite parity. But that is
impossible, since k and p are odd, a and b are even,
and each of (a-b,a+b) is even.

Next, we prove that (k + 1)/5 cannot be an integer.
Suppose, on the contrary, that k = -1 mod 5. Then
a^2 - b^2 = k^m - k^n = +/-2 mod 5,
since m and n have opposite parity.
Every square is congruent to an element of {-1,0,1}
modulo 5. Hence we must have a^2 = -b^2 = +/-1 mod 5.
The residues of a^2 + k^n and b^2 + k^m must therefore
lie in the set {-2,0,2} modulo 5, with 0 being the only
possibility for a common residue, since each of the sets
{a^2,b^2} and {k^n,k^m} is congruent to {-1,1} modulo 5.
By inspection there is only one solution to
5 = a^2 + k^n with positive integers (a,k,n) and k = -1 mod 5,
namely a = 1, k = 4, n = 1. Thus p is a composite number,
divisible by 5, contra hyp.

Finally, we prove that (k + 7)/16 cannot be an integer.
Suppose, on the contrary, that k = -7 mod 16. Then
the set {k^m,k^n} is congruent to {-7,1} modulo 16,
since m and n have opposite parity. Hence
a^2 - b^2 = k^m - k^n = 8 mod 16.
But that is impossible, since each of (a,b) is even
and every square of an even number is congruent to an
element of {0,4} modulo 16.

Hence we have completed the proof that no element
of S(k) is integral, k is not a square, m - n is odd.

Motivation of the conjecture:
*****************************
For each positive integer k < 10^4 such that
k is not a square and no element of S(k) is
integral we have found at least 2
BPSW probable primes of the form
p = a^2 + k^m = b^2 + k^n
with positive integers (a,b,m,n) and a > b.

For any such k, we expect the number of primes
of this form with p < x to grow faster than
log(log(x)), asymptotically, since one expects
O(log(log(x))) primes p < x of the form
p = (k^n*A/2 + B/2)^2 + k^n = (k^n*A/2 - B/2)^2 + k^(n+d)
for fixed odd d = m - n > 0 and a fixed factorization of
k^d - 1 = A*B, chosen so as to make p prime for at least
one positive value of n.

We also conjecture that there is an infinitude of primes of the form

p = ((k-1)*k^n/4 + 1)^2 + k^n = ((k-1)*k^n/4 - 1)^2 + k^(n+1) [*]

whenever k is a positive integer congruent to an element of
{5,13,21,37} modulo 40, or a non-square positive integer
congruent to an element of {0,2,6,8} modulo 10.
Such primes have easy proofs, thanks to Pocklington's theorem.

Notable examples of Pocklington proofs of primes of the form [*],
with more than 80,000 decimal digits, are provided by

http://primes.utm.edu/primes/page.php?id=78125
http://primes.utm.edu/primes/page.php?id=78195

with k = 2 and k = 61, respectively.

The cases with a non-square positive integer k congruent
to an element of {1,17,33,65} modulo 80 do not appear to have
BLS-provable forms, at large sizes. However it is easy to find
gigantic probable primes. For example,

(x + 1)*(4*x + 5) - 1 = (2*x + 2)^2 + x = (2*x - 2)^2 + 17*x

with x = 17^4478 gives a probable prime with 11,021 decimal digits.

David Broadhurst and Mike Oakes, 29 July 2006