Question: I feel this is an intuitive result.
If, for example, I was working with the prime number $11$, I could split it in the following ways: $\{1, 10\}$, $\{2, 9\}$, $\{3, 8\}$, $\{4, 7\}$, $\{5, 6\}$.

Then clearly there is no way that the $2$ numbers can have a $\gcd$ of anything other than $1$. However, I am sort of lost on how to start a formal proof for this. Any pointers would be much appreciated.

Answer: 
Let $d$ be their gcd.
Then $d$ divides their sum $p$,
so $d$ can be only 1 or $p$.

If $d = p$, then $p$ divides both $a$ and $b$.
Since both of these are positive,
they are each at least $p$,
so their sum is at least $2p$.

I realize that this is a restatement of mixedmath's answer.

This can easily be generalized to show that
this holds for the sum of $k$ positive integers
for $k \ge 2$.
As $(a,b) \mid a$ and $(a,b) \mid b,\ \ (a,b) \mid (pa+qb)$ where a,b,p,q are integers.

If (a,b) is not prime, $pa+qb$ can not be prime.

So, if $pa+qb$ is prime, (a,b) must be.

But there exists, p,q of opposite parity such that $(a,b)=pa+qb$ (which is [Bézout's Identity](http://mathworld.wolfram.com/BezoutsIdentity.html)).

In that case, primality nature of $pa+qb$ will be dictated by that of $(a,b)$.