# If all pairs of addends that sum up to $N$ are coprime, then $N$ is prime.

I think this must be a known theorem, but I've tried searching for it on google without much luck. I would state it as follows:

If for all possible pairs of addends that sum to the same number N each of those pairs is comprised of two numbers that are coprime, then N is prime.

It is the inverse of that which was discussed/proved here: If the sum of positive integers $a$ and $b$ is a prime, their gcd is $1$. Proof? Instead of starting with a prime number and wanting to prove that any two numbers summing to it are coprime, in this case I'm starting with a set of addend pairs that sum to the same number, noticing that those addend pairs are always coprimes, and wanting to come to the conclusion that the common sum must be a prime.

I would also like to know what this theorem is called if it is indeed a known theorem.

• Thanks for the proofs below, but it's more that I'm looking for someone to attribute/cite. – Robert Gross Jun 4 '15 at 22:23
• What do you mean? If you must, you can cite us. It's a two-line proof. – davidlowryduda Jun 10 '15 at 2:53

Hint: If a number is not prime, say $n = ab$ where $a,b > 1$, what can you say about $b$ and $(a-1)b$?
If $N$ is not prime, then there exists a pair of addends $X,Y$ summing to $N$ such that $X$ and $Y$ are not coprime.
Let $N = ab$ where $a, b> 1$ (since $N$ is composite). Then we can take $X = a(b-1)$ and $Y = a$, so that $X + Y = ab = N$ and $\gcd(X,Y) = a > 1$. This completes the proof. $\diamondsuit$