Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime. 
Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime.

Though I didn't check the statement with so many integers, but it looks like the equation never returns a prime. 
 A: The only counterexamples to your claim are the cases where $m=1$ and $a+1$ is a prime, and the case where $a=1$ and $m$ is any positive integer.
If $m$ is odd, then you can use the factorisation
$$a^m+1=(a+1)(a^{m-1}-a^{m-2}+a^{m-3}-...-a+1)$$
to conclude that $a^m+1$ is divisible by $a+1$ and hence is not prime. (Unless possibly $m=1$ and $a+1$ happens to be prime)
If $m$ is even, then $a$ must be odd since $\gcd(a,m)=1$. But then $a^m+1$ is even, and so can only be prime if it is equal to $2$.

Edit
It should of course be mentioned that the above shows that if $a^m+1$ is prime for some $m$ then it must be the case that $m$ is a power of $2$. (If $m$ has some odd divisor then we could use the same factorisation as is used above to find a factor or $a^m+1$) Beyond this, however, very little is known if we drop your restriction that $\gcd(a,m)=1$.
If $a=2$ then the numbers which we consider by taking $m=2^k$ a power of $2$ are the Fermat Numbers. We do not know if any such numbers are prime for $k>4$, and there are at this time (according to the Wikipedia article) only $280$ Fermat numbers which are known to be composite.
We do not know if there are infinitely many Fermat numbers which are prime. We do not even know if there are infinitely many Fermat numbers which are composite, and of course one of these two propositions must be true.
The general case with $a$ as the base is just as poorly understood. As far as I know, there is not a single value of $a$ for which it is known whether or not there are infinitely many primes of the form $a^{2^k}+1$. (Other than the cases where $a$ is odd or $a$ is an odd power of some integer, where the same argument as the one above shows that all such values are composite), and the list of values of $a$ and $k$ for which it is known whether $a^{2^k}+1$ is prime or composite is just as short as the list of known Fermat primes.
