If p = a^2 + 1 and q = b^2 + 1 (a < b), then we have :
p q = (a b – 1)^2 + (a + b)^2 and p q = (a b + 1)^2 +
(b – a)^2 (*).
Assume p q = c^2 + 1. It would be wrong to conclude that b – a =
1. Indeed, for instance, a = 2 and b = 8 give : p = 5, q = 65 and p
q = 325 = 18^2 + 1 while (*) gives here : p q = 15^2 + 10^2 = 17^2 +
The point is, that when p and/or q is NOT prime, there are more
than two representations for p q as a sum of two squares, while
when p and q are both primes, the representations (*) are the only
ones (see this for instance in http://mathworld.wolfram.com/SumofSquaresFunction.html
or in any decent tekstbook of Number Theory). Thus, in that case, b –
a will be 1, which is indeed only possible when p = 2 and q = 5.
If p = a^2 + k^2 and q = b^2 + k^2 (with k > 1), we have :
p q = (a b – k^2)^2 + (a k + b k)^2 = (a b + k)^2 + (a k
– b k)^2 (**).
If at least one of the numbers p, q is NOT prime, then these two
representations are not unique. If p and q are both prime, then
the representations (**) are again the only ones, and hence, when p q
= c^2 + k^2, we have b = a+1, which is not possible
since p and q cannot have the same parity.
I'm afraid that the problem cannot be solved without knowledge
about the number of representations of a natural number as a sum of
two squares. But, the next question is one that can be answered by
computer (and could be more suitable for the puzzlers) :
If m = a^2 + k^2 is NOT prime, is it possible
that EVERY prime divisor of m can be written as c^2 + k^2 for
some c ?
The answer is yes when k = 1 (smallest m = 10)
k = 2 ( " m =
k = 3 ( " m =
k = 4 ( " m =
k = 5 ( " m =
k = 6 ( " m =
For k = 7, 8, 9 I could not find such an m (however I think there
will be fairly big ones). For k = 10, 11, 14, 15, 16 and 20, I
found relatively small m.
The result of puzzle 582 is 'hidden' in the results of this problem,
since no m will be the product of two different primes, unless m =