11
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – achacttn Aug 12 '12 at 0:58
  • 2
    $\begingroup$ @achacttn: As $a',b' \geq 1$, we know $a' + b' \geq 2$. Thus $a + b \geq 2d$. $\endgroup$ – davidlowryduda Aug 12 '12 at 1:02
  • $\begingroup$ ah understood. Thank you $\endgroup$ – achacttn Aug 12 '12 at 1:44
  • $\begingroup$ Hello davidlowryduda, could I please get your thoughts on my answer? Is it wrong? Someone voted to delete it. $\endgroup$ – user198044 Oct 10 '18 at 14:19
13
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Aug 12 '12 at 0:20
  • $\begingroup$ How do you know that c would be 1 then? $\endgroup$ – achacttn Aug 12 '12 at 0:42
  • 4
    $\begingroup$ @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. $\endgroup$ – davidlowryduda Aug 12 '12 at 1:01
  • 2
    $\begingroup$ @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. $\endgroup$ – stefan Aug 12 '12 at 14:23
  • $\begingroup$ @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. $\endgroup$ – Gerry Myerson Aug 12 '12 at 23:29
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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<a+b=p$. Thus, $d=1$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$$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<p$. Any particular reason someone voted to delete this answer?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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