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

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


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.


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