Non prime number test Suppose $a\geq 3, n\geq 3$ are integers. I claim that if $gcd(a, n)=1$, then $a^n+n^a$ is not a prime. I am trying find a counter example but till now I did not reach there. 
 A: $a=24,n=5$ gives $$59\ 604\ 644\ 783\ 353\ 249$$, which is prime.
You asked in a comment how we know these are primes. Software. The exceptions to your conjecture are all fairly big. The next biggest after 5,24 and 3,56 include 54,7 and 69,8 and 76,9 and 15,32 etc. Manual calculation is not feasible. 
Of course one might try to construct by hand a reason why there are (probably) infinitely many cases, but you did not ask for that. You just asked whether there were counter-examples.
A: The following PARI/GP-program shows the pairs $3\le a<n\le 100$ with $gcd(a,n)=1$, such that $a^n+n^a$ is prime. The smallest prime occuring is $5^{24}+24^5$.
? for(a=3,100,for(n=a+1,100,if((gcd(a,n)==1)*(isprime(a^n+n^a,2)==1),print(a," "
,n))))
3 56
5 24
7 54
8 69
9 76
15 32
21 68
33 38
34 75
56 87
80 81
?

So, the claim is false, but the smallest prime has $17$ digits. 
Hand calculation would not be completely impossible, but it would take very long and the danger of an error would be great. 
A strong pseudoprime-test to base $2$ could be done by hand, but it would still be difficult to actually do that. 
A: Take for example $a=3,n=56$. Then $3^{56}+56^3$ is prime.
Another example $a=5,n=1036.$ Then $5^{1036}+1036^5$ is prime, as well.
