My first approach was to consider modulo 6.
Assume a > 6, Since a is prime we have a=1, -1 (mod 6)
Thus, a2=1 (mod 6).
We know, 26 = 2 (mod 6)
Therefore a2+26=3 (mod 6)
So any prime greater than 6 would be resulting in a number which is divisible by 3 which NOT prime as required.
So we have to check 2, 3 and 5 which are the only primes less than 6. It is easy to see that each would yield a non-prime in a2+26. So we're done!