Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 9 down vote accepted

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

share|cite|improve this answer
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$. – mixedmath Aug 12 '12 at 1:02
ah understood. Thank you – achacttn Aug 12 '12 at 1:44

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

share|cite|improve this answer
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. – mixedmath Aug 12 '12 at 1:01
Thanks very much! – achacttn Aug 12 '12 at 1:46
@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

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

share|cite|improve this answer

As $(a,b)|a$ and $(a,b)|b,\ \ (a,b)|(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)$.

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.