If the sum of positive integers $a$ and $b$ is a prime, their gcd is $1$. Proof?

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 1

Let's show the contrapositive, because why not?

So we want to show that if $a,b>0$ and $\gcd(a,b) \neq 1$, then their sum is not prime.

Suppose that $\gcd(a,b) = d > 1$. Then $a = a'd$ and $b = b'd$ for some $a',b'$ natural numbers. But then $a + b = da' + db' = d(a' + b')$, and as each of $d,a',b' \geq 1$, we have that $a + b \geq 2d$, but is divisible by $d$. Thus it is not prime. $\diamondsuit$

Thus if the sum of positive integers is prime, then their gcd is $1$.

Answer 2

Let $c$ be the gcd. Then $c$ divides $a$ and $b$, hence it divides $a+b$, a prime number.

Answer 3

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$.

Answer 4

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).

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