Problems & Puzzles: Puzzles

Puzzle 1089 17=2^3 + 3^2 JM Bergot sent the following nice puzzle. I've noticed other strange facts about prime 17=2^3 + 3^2 using just primes 2 and 3. Q. Can you find more examples using that very algebraic form?

---

During the week from 4 to 10 of June, contributions came from Paul Cleary, Adam Stinchcombe, Giorgos Kalogeropoulos, Jim Howell, Simon Cavegn

***

Paul wrote:

There are no other examples.

 

When both primes are odd:-

 

a prime to the power of another prime is always odd thus the sum of 2 of them will always be even and thus a composite.

 

When one prime is 2 and the other is an odd prime:-

 

2^Prime[p] Mod 3 is 2 for all odd primes p and

Prime[p]^2 Mod 3 is 1 for all Primes[p] except when p = 3 with a residue of 0.

 

Thus the sum of all residue combinations will be 3 except for the one case when it is 2.  17 Mod 3 is 2 and for all other odd primes will be divisible by 3 and thus a composite.

***

Adam wrote:

If p and q are both odd primes, then p^q+q^p is even and not prime.  So one of the primes is 2 and we are looking for when 2^p+p^2 a prime.  For primes of the form 6n+1 or 6n-1, mod 3 this is (-1)^p+p^2 which is -1+1 =0.  Ergo, the only possible p are primes not of the form 6n+/-1, so our candidates are 2 (not prime) and 3 (abracadabra).

 

***

Giorgios wrote:

We are searching for primes S of the form S = p^q + q^p where p and q are primes.

It is obvious that one of p^q and q^p must be even.

So, S = 2^p + p^2.

Now, if we work mod 3 we get:

2^p mod 3 = (-1)^p mod 3 = -1 mod 3 because p is odd.

Also, p=+/-1 mod 3 and p^2 = 1 mod 3 for any prime p>3

S = 2^p + p^2 = (-1) + 1 mod 3 = 0 mod 3

S is always divisible by 3 for any prime p>3.

17=2^3 + 3^2 is the only case

 

***

Jim wrote:

In puzzle 1089, I don’t know what “strange facts” JM Bergot is talking about…

 

I will assume that the puzzle asks for solutions to the equation:

 

n = p^q + q^p

 

where p, q, and n are all prime.

 

The only solution is the one given, namely 17 = 2^3 + 3^2

 

Proof:

If p and q are both prime, then:

 

If both are odd, then n = odd + odd = even (and greater than 2), so not prime.

(Example:  3^5 + 5^3 = 243 + 125 = 368)

 

Therefore, one of them must be 2.  Call that one p.

 

So, p = 2 and the equation becomes:

 

n = 2^q + q^2

 

If q = 2, then n = 8

 

If q = 3, then n = 17, which is the given solution.

 

For all other values of q (prime and greater than 3), we have:

 

2^q = 2 mod 3 (true for all odd q)

    and

q^2 = 1 mod 3 (since q is not divisible by 3)

 

Therefore, n = 2 + 1 = 3 = 0 mod 3

So n is divisible by 3 (and greater than 3), so it is not prime.

 

Example:   2^5 + 5^2 = 32 + 25 = 57 = 3*19

***

Simon wrote:

n = p^q + q^p, (n,p,q all prime)
=> For n to be odd, exactly one summand must be odd. This means either p or q must be the only even prime 2.
Tested: For p=2 and q=the first 4000000 primes and n>17, n is divisible by 3.
Conjecture: There are no more solutions of the form n = p^q + q^p, (n,p,q all prime) other than 17 = 2^3 + 3^2, because every odd n except 17 of this form is divisible by 3.

***