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

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.

• Hint: The gcd can't be $a+b$, but must divide $a+b$. – Geoff Robinson Aug 12 '12 at 0:09
• Note that positive does need to be used. For $\gcd(9,-6)=3$, and $9+(-6)$ is prime. – André Nicolas Aug 12 '12 at 0:10

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

• Thanks for your reply. I understood your post up to "as each of d,a′,b′≥1", but couldn't see how it was immediately followed by "we have that a+b≥2d". – achacttn Aug 12 '12 at 0:58
• @achacttn: As $a',b' \geq 1$, we know $a' + b' \geq 2$. Thus $a + b \geq 2d$. – davidlowryduda Aug 12 '12 at 1:02
• ah understood. Thank you – achacttn Aug 12 '12 at 1:44
• Hello davidlowryduda, could I please get your thoughts on my answer? Is it wrong? Someone voted to delete it. – user198044 Oct 10 '18 at 14:19

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

• And where have you used the hypothesis that $a$ and $b$ are positive? The result is false without that hypothesis, as Andre noted in the comments, so you must have used it somewhere. – Gerry Myerson Aug 12 '12 at 0:20
• How do you know that c would be 1 then? – achacttn Aug 12 '12 at 0:42
• @achactnn: His theory was that since $c$ divides a prime number, it must be $1$. But this proof is incomplete (despite its many upvotes) because it doesn't use positivity. For example, let's use Andre's counterexample in Eepzy's answer. Let $3$ be the gcd. Then $3$ divides $9$ and $-6$, and thus $9 - 6 = 3$, a prime number. This is consistent with his reasoning, but it doesn't guarantee that $c$ would be $1$ (as written), at least not without a positivity assumption. – davidlowryduda Aug 12 '12 at 1:01
• @GerryMyerson: That's easy to solve: c is either 1 or (a+b) since (a+b) is prime. If a and b > 0, then a+b cannot be a divisor of a or b, thus c == 1. – stefan Aug 12 '12 at 14:23
• @stefan, yes, it's easy to plug the hole in Eepzy's work - I'm just noting that there is a hole, and it needs plugging. – Gerry Myerson Aug 12 '12 at 23:29

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

Here is a direct proof that is independent of the others:

Let $g = \gcd(a,b)$. Then we can see that $$g\mathbb{Z} = a\mathbb{Z} + b\mathbb{Z} = \{n\in \mathbb{Z} | ra + sb = n, \text{for } r,s \in \mathbb{Z} \}.$$

In other words, $g$ generates the set of all integer combinations of $a$ and $b$. (If you are not familiar with this, it is most likely presented as a theorem in your textbook.) Since we are $a+b=p$ (given) and $a+b$ is some integer combination of $a$ and $b$, then $p$ must be in $g\mathbb{Z}$.

If $p \in g\mathbb{Z}$, then $g$ must be equal to $1$ or $p$ (since $p$ is prime). But by the fact that $a$ and $b$ are both positive and less than $p$ (the sum of the two equals $p$), then $p$ can't possibly be the greatest common divisor, let alone a divisor of any kind. Therefore $g = 1$.

Suppose $a,b$ are positive integers whose sum is a prime, $p$. Then $a+b = p$. Also, because $a, b$ are both positive integers that add up to $p$, then $a,b < p$. This implies that $\gcd(a,p) = 1$ and $\gcd(b,p) = 1$. Thus we can write 1 as a linear combination of both $a$ and $p$ or $b$ and $p$. Let us do it the first way. $ax + py = 1$ for some $x, y \in \mathbb{Z}$. From our original assumption, $a+b = p$. Thus we can substitute. $ax + (a+b)y = 1$. This implies $ax + ay +by = 1$. Grouping like terms we get $a(x+y) + b(y) = 1$. Thus 1 can be written as a linear combination of $a$ and $b$. This implies that $\gcd(a,b) = 1$. We have shown what we wanted to show.

let prime p=a+b, a and b positive

Suppose gcd(a,b)=s, $s\ne 1$

Then s divides a and s divides b, so there are some m,n such that a=sm and b=sn

then $a+b=sm+sn=s(m+n)$, which shows that s is a factor of a+b

so s is a factor of p. Contradiction.

The way out for negatives is that, in the above example, 3 is a factor of p, since it is p itself. So there is no contradiction in that case.

Complete short proof:

Let $$\gcd(a,b)=d$$. Then, $$d \mid a$$ and $$d \mid b$$. Thus, $$d \mid a+b=p$$. Thus, $$d=1$$ or $$d=p$$. Since $$d \mid a$$, $$d\le a. Thus, $$d=1$$.

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

$$1=\gcd(p,a)=\gcd(a+b,a)=\gcd(a,b)$$

The last step follows from $$\gcd(b+ma,a)=\gcd(a,b)$$ for any integer $$m$$. The first step follows from $$a. Any particular reason someone voted to delete this answer?