Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

Any two positive integers are co-prime if their sum is a prime number

Is this a trivial thing to say? I have a proof, but I don't want to bore anyone if it's just a trivial matter-of-fact thing about primes and co-primes.

share|cite|improve this question

marked as duplicate by Marc van Leeuwen, Dominic Michaelis, user1729, Davide Giraudo, draks ... Mar 15 '13 at 11:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

It's false. $15+(-12)=3$. – Gerry Myerson Mar 14 '13 at 11:57
That was quick... I guess I was thinking about positive numbers so I'm sorry for not saying that. I'll go away and rethink my question a bit better!! – Andy aka Mar 14 '13 at 12:02
Change "integers" to "natural numbers", and you've got it. It's easy to prove by contrapositive. – Shaun Ault Mar 14 '13 at 12:11
I was just thinking about positive integers being co-prime if their sum is a prime number. I still think it's trivial what i'm asserting but i've not seen it on any math websites. – Andy aka Mar 14 '13 at 12:12
Shaun, thank you for your answer. I am certainly no mathematician so if you could show me your proof I'd appreciate it. My proof: Consider (p+n) and (p-n) where n is an odd integer and p is a prime greater than 2. Because p is prime, (p+n) and (p-n) cannot exactly divide by n. GCD (p+n, p-n) = 2 therefore, (p+n)/2 and (p-n)/2 are co-prime. – Andy aka Mar 14 '13 at 12:14

3 Answers 3

When both integers are positive, this is a special case of the converse to Bézout's theorem (labeled (ii) on the linked page).

If $a+b=p$, that theorem (with $x=y=1$) tells us that $\gcd(a,b)$ must be a divisor of $p$. But if $p$ is prime, that means $\gcd(a,b)$ is either $p$ or $1$.

Moreover, if $a$ and $b$ are both positive, then $a+b=p$ implies that $a$ and $b$ are both smaller than $p$, so they cannot have $p$ as a divisor. So $\gcd(a,b)=1$.

share|cite|improve this answer
Thanks Micah and thanks for introducing me to Bezout's theorem. I am a relative novice to these things and i do appreciate you guys giving up your time to comment. – Andy aka Mar 14 '13 at 15:08
This appears wrong. What do you mean when you write: "Bézout's theorem (with $x=y=1$) tells us that $\gcd(a,b)$ must be a divisor of $p$"? – Math Gems Mar 16 '13 at 1:43
@MathGems: I mean that $p$ is an integer linear combination of $a$ and $b$. Thus it is a multiple of their gcd. – Micah Mar 16 '13 at 3:58
That's not Bezout's theorem. That $\rm\:d\mid a,b\:\Rightarrow\:d\mid a+b\:$ is true in any ring and has nothing to do with Bezout's theorem, which says that $\rm\:gcd(a,b)\, =\, j\, a + k\,b\:$ for some $\rm\:j,k\in \Bbb Z.\:$ – Math Gems Mar 16 '13 at 4:12

I don't think it's a trivial thing to say, in fact, I have never seen that statement before. As for a proof, I don't know what yours looks like, but I'd do the following:

Let $x$ and $y$ be positive integers such that $x + y$ is prime. Suppose $x$ and $y$ are not coprime, that is, there is some integer $k > 1$ such that $x = ka$ and $y = kb$ for some positive integers $a$ and $b$. Then $x + y = ka + kb = k(a+b)$, which is a contradiction as $a + b >1$ and $x+y$ is prime.

share|cite|improve this answer
Thanks Michael. I now think it is a trivial thing to prove but why you or I have never seen it written down surprises me (given the number of websites that seem to spout knowledge about primes and co-primes. Thanks again. – Andy aka Mar 14 '13 at 15:06

Yes, it is trivial. It is a consequence of $\rm\:(a,n\!-\!a)\, =\, (a,n),\:$ in the special case when the gcd $=1.\:$ Namely, in your case, $\rm\ a+b \,=\, n\:$ and $\rm\ 0< a,b\:\Rightarrow\: a,b<n,\:$ so $\rm\:(a,n) =1\: $ when $\rm\:n\:$ is prime, therefore $\rm\,\ (a,b)\, =\, (a,n\!-\!a) \,=\, (a,n) \,=\, 1.\ $

Generally $\rm\: (a,n\!+\!ak)\, =\, (a,n)\: $ since if $\rm\: d\mid a\ $ then $\rm\: d\mid n\!+\!ak\!\iff\! d\mid n.\, $ So $\rm\:a,n\!+\!ak\:$ and $\rm\:a,n\:$ have the same set $\rm\,D\,$ of common divisors $\rm\,d,\,$ so the same greatest common divisor $\rm(= max\ D).\:$ Notice that this is precisely the inductive (descent) step in the Euclidean algorithm for the gcd. Therefore your result also follows by applying Euclid's algorithm to compute the gcd $\rm\, (a,a\!+\!b)$

share|cite|improve this answer
I'm answering my own question with a link to another page in stack exchange that asks the same question. I don't think anyone need worry about this anymore unless there's something particularly useful to say that hasn't been said already. Thanks guys for the excellent feedback and promptness.… – Andy aka Mar 14 '13 at 18:48

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