Inspired by a Black Pen Red Pen video on Youtube where he proved that $4^{2019}+2019^4$ is not prime using the Sophie Germain identity, I began exploring when numbers of the form $a^b+b^a;a,b\in\mathbb{N}$ are prime. Without loss of generality, I restrict it to $a\leq b$.
It is trivial to see that there are an infinitude of primes where $a=1$. I then discovered from OEIS that numbers of the form $a^b+b^a;a,b\in\mathbb{N}\setminus1$ are called Leyland numbers, and that the sequence of known Leyland primes (in addition to 3) is sequence A094133 on OEIS, and can be found on Leyland's website in a table along with Leyland PRPs. http://www.leyland.vispa.com/numth/primes/xyyx.htm.
What I wanted to do is to find criteria that will indicate whether or not a Leyland number is prime. The first obvious criteria I found is that if $GCD(a,b)=n>1$, then $a^b+b^a\equiv0 \mod n$, and therefore $a,b$ must be coprime. The second obvious criteria was that $a+b$ must be odd, because otherwise $a^b+b^a$ would be even.
I then proceeded to explore further to try to find limitations on which values for $a$ will never result in a Leyland prime, and if there were any values of $a$ for which a prime or composite number for $b$ will always or will never return a Leyland prime.
What I have found so far:
For $a=2$, a necessary condition for $a^b+b^a$ to be prime is that $b\equiv3\mod 6$, because if $b$ is even then $a^b+b^a$ will also be even, and if $b$ is odd but not divisible by 3, then $a^b+b^a$ will be divisible by 3. However, the condition that $b\equiv3\mod 6$ is not sufficient for $a^b+b^a$ to be a Leyland prime, as for example $2^{27}+27^2=73\times521\times3529$.
For $a=4$, there are no Leyland primes. This can be proven, as for odd $b$, $4^b+b^4$ is factorable using the Sophie Germain identity, and for even $b$, $4^b+b^4$ is even.
For $a=6$, I have not found any Leyland primes, but cannot prove that they don't exist. As $a,b$ must be coprime, we get that $b$ must be odd but not divisible by 3. An additional criteria is that $b$ must be divisible by 7, because $6^b\equiv-1\mod7$ for any odd $b$, and $b^6\equiv1\mod7$ for any $b$ which is not divisible by 7. Therefore, all that remains is to test for $b\equiv7\mod42$ and $b\equiv35\mod42$. Looking at the table on Leyland's website, I have not found any pattern that I can use to prove that there are no such Leyland primes, although if any exist, they must be with $b>7500$ or slipped through the cracks of the computations.
All other single digit numbers produce at least one Leyland prime, but I do not see any pattern to determine when they will or won't produce Leyland primes (other than the trivial criteria mentioned above).
Does anyone have any insights for how to determine more precise criteria for how to produce Leyland primes?
