Prime, Prime, and Prime

$p$ and $q$ can't be two odd numbers, because then $p^q+q^p$ would be an even number, greater than $2$ , so not a prime. $p=q=2$ is not a solution, so suppose $p\geq q$ . Then $q=2$ for sure. Now $p^2+2^p$ has to be a prime, where p is an odd prime. If we try with $p=3$ , then $2^3+3^2=17$ is a prime, so we get a solution. If we try with $p=5$ , we get $2^5+5^2=57$ is not a prime, since it is divisible for example with 3. If we try with $p=7$ we get an other wrong solution, $2^7+7^2$ is also divisible by $3$ . The suspicion arises that the only solution is $p=3$ , because the others are divisible by $3$ . We will prove our notice!

Note that if $k$ is an odd integer, then $k^2\equiv1 \ \mod3 \ \forall \ k>0, 3\not\mid k$ . So $p^2\equiv1 \ \mod3$ .

Since $2^p=2^{2n}*2$ and $4\equiv1 \ \mod3 \Rightarrow 2^{2m}\equiv1 \ \mod3 \ \forall \ m\geq0$ , it is obvious that $2^p=2*2^{2n}\equiv1*2=2 \ \mod3$ .

So if $p\neq3$ , then $3\mid p^q+q^p$ .

Therefore the only solution is $p=3, q=2$ (because $p\geq0$ ) and the answer is $\boxed{22}$ .

First we nottice that $p,q$ can't be odd simultaneously, but both of them have to be prime so $p=2$ (if we choosed $q=2$ this wouldn't change because of the problem symmetry)

Analysing the expression $2^{q} + q^{2}$ we can see that $q=3$ is a solution since the sum gives us $17$ , my hypothesis by looking at the other sums that $q$ is prime it's that this is the only solution, so i have to prove it. We can see that $q^{2} \equiv 1 \mod 3$ by Fermat's Little Theorem if $q$ is not a multiple of 3, analysing the term $2^{q}$ (Note that q haves to be odd) we can see that $2^{q} \equiv -1 \mod 3$ so $2^{q} + q^{2} \equiv (-1) + (1) \mod 3$ if $q$ is odd and not a multiple of $3$ so all other primes that aren't $3$ won't work, so answer is $2 + 3 + 2^{3} + 3^{2} = 22$

The answer is 22.

Why?

Well first of all - in order for $p^q + q^p$ to be a prime number, it must be odd.

It follows that either p or q must be even and the only even prime that I know of is 2. so we are actually asked here what is the largest $2^q + q^2$ that is prime where q is of course prime. the truth is that very fast (q>3) this $2^q + q^2$ is becoming always divisible by 3....

How do I know?

Well let's start with the easy part - let's focus on $2^q$ .
I shall prove by induction that $2^q\equiv\ 2 \ mod \ 3$ . Starting with q=1 we can see that indeed $2^1=2$ . Now suppose that we proved that $2^q\equiv2 \ mod\ 3$ so the next one would be q+2 because q is obviously odd... and for $2^{q+2}\equiv2 \ mod\ 3$ we actually have $2^{q+2}\equiv4*2^q\equiv4*2\equiv8\equiv2 \ mod\ 3$

Now for the tougher part... - how do I know that $q^2\equiv1\ mod\ 3$ ? Well every integer can be one of the following: $6k-1$ , $6k$ , $6k+1$ , $6k+2$ , $6k+3$ or $6k+4$ . Of these: $6k$ is divisible by 6 $6k+2$ is divisible by 2 $6k+3$ is divisible by 3 $6k+4$ is divisible by 2

So a prime number greater equal 6 can only be either $6k-1$ or $6k+1$ .

Now squaring this we get $(6k+1)^2 \equiv 36k^2+12k +1 \equiv 1\ mod\ 6$ .

and $(6k-1)^2 \equiv 36k^2-12k +1 \equiv 1\ mod\ 6$ .

In other words a square of a prime number has modulo 1 when divided by 6.

or in other other words a square of a prime number has a modulo 1 when divided by 3. which means $q^2\equiv1\ mod\ 3$ with one exception... - for the prime number 2

So to sum it up: $2^q + q^2\ \equiv\ 2 + 1\ \equiv\ 3\ \equiv 0\ mod\ 3$

Now as explained above the exception is with numbers smaller than 6:

for q=5 we get $p^q+q^p=2^5+5^2=57$ which is not a prime.

q=4 is not prime.

for q=3 we get $p^q+q^p=2^3+3^2=17$ which is a prime and is the largest we can get.

So we are looking for $p + q + p^q + q^p = 2 + 3 + 2^3 + 3^2 = \boxed{22}$