Problems & Puzzles: Puzzles

Puzzle 582. p.q=c^2+1 Emmanuel Vantieghem sent the following puzzle: It is not difficult to find two numbers of the form  x^2 + 1  whose product is also of the form  x^2 + 1.  For instance : 2 = 1^2 + 1, 5 = 2^2 + 1, product = 10 = 3^2 + 1,             5 = 2^2 + 1, 65 = 8^2 + 1, product = 325 = 18^2 + 1             10 = 3^2 + 1, 17 = 4^2 + 1, product = 170 = 13^2 + 1               .....                       ..... Q1. Are there besides  2  and  5, other numbers  p = a^2 +1  and  q = b^2+1 (b > a), both prime, such that  the semiprime  p.q  can be written in the form  c^2+1 ? Q2. Can you find primes p, q,  p = a^2+k^2, q =b^2 + k^2 such that  p.q = c^2+k^2 ?

---

Contributions came from Antoine Verroken.

***

Antoine wrote:

Q1.      ( a^2 + 1 ) * ( b^2 + 1 ) = c^2 + 1 = ( a*b -+ 1 )^2 + ( a +- b )^2      (1)

            1.         (1)       a – b = 1, a=1+b,          (2)

            2.          a*b – 1 = 1      a*b = 2      a = 2      b = 1        (3)

            3.         (2) (1)  the difference of the two primes : 2*b + 1 is odd ; one of the 2 primes must be 2  à  b^2 + 1 = 2      b = 1      a = 2     c = 3 ; there is only 1 solution for (1)

***

Emmanuel Vantieghem, the puzzle´s author wrote:

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 + 6^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 = 125)

                                     k = 3 (    "        m = 5224109293)

                                     k = 4 (    "        m = 28577)

                                     k = 5 (    "        m = 334109)

                                     k = 6 (    "        m = 137677).

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 = 10.

***

 

---