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.

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) > = 1$ or $\gcd(a+b, a-b) = 2$ holds.

I think the first step should look something like this:

$d = \gcd(a+b, a-b) = \gcd(2a, a-b)$

From here I tried to proceed with two cases.
1: $a-b$ is even, which leads to $\gcd(a+b, a-b) = 2$
2: $a-b$ is odd, which leads to $\gcd(a+b, a-b) = 1$

My main problem I think is, that I do not know how I should include $\gcd(a,b) = 1$ in the proof.

Any help is appreciated. Thx in advance.
Cherio Woltan

share|cite|improve this question
$x=(a-b,2b)=(a-b,2a)\,\Rightarrow\, x=(a-b,2(a,b))=(a-b,2)\mid 2$. – user236182 Sep 18 at 16:32

6 Answers 6

up vote 16 down vote accepted

Let $d$ be a common divisor of $a+b$ and $a-b$, then $d$ divides their sum $2a$ and difference $2b$. If a number divides two numbers it also divides their gcd, thus $d$ divides $2\text{gcd}(a,b) = 2$. That implies that every divisor (including the greatest common divisor) is a divisor of $2$.

The same argument again in symbols:

Let $d | a+b, a-b$, then $d | (a+b)+(a-b) = 2a$ and $d | (a+b)-(a-b) = 2b$ so $d | \text{gcd}(2a,2b) = 2$.

share|cite|improve this answer
Great! I had to think a little about your prove but hopefully now I got it. Thx again... – Woltan Apr 13 '11 at 13:02

I advise not doing a proof by cases. That was my initial attempt, but I found myself going through a logical rabbit hole with no end in sight. I suggest attempting to show that the common divisor, call it $d$, satisfies $d\leq2$, which implies that $d=1$ or $2$.

Here is a proof using the above strategy. Here are a few lemmas that will assist us in our deductions.

I adopt the notation $gcd(a,b) = (a,b)$.

$\enspace$$\enspace$Lemma 1 If $a|b$ and $b\neq0$, then $|a| \leq |b|$

$\enspace$$\enspace$Lemma 2 If $a|b$ and $a|c$, then for every integer $m$ and $n$, $a|(mb+nc)$

$\enspace$$\enspace$Lemma 3 For every integer $a$,$b$ and $c$, $(a+bc,b)=(a,b)$

$\enspace$$\enspace$ Lemma 4 For every integer $a$ and $b$, there are integers $x$ and $y$ such that $ax+by=1$

Now for the proof.

Proof: Suppose $(a,b)=1$. Then from lemma 4, there are integers $x$ and $y$ such that

$$ax+by=1 \tag{1}$$

Let $d=(a+b,a-b)$ (Recall that $d>0$ by definition.

From lemma 3, we can write

$$d=(2a,a-b)$$ $$d=(2b,a-b)$$

Since $d$ is the greatest common divisor of $2a$, $a-b$, and $2b$, it follows that $d$ also divides each of them. In particular, $d|2a$ and $d|2b$. Hence, from lemma 2, we know that $d|(2am+2bn)$ for arbitrary integers $m$ and $n$.

By lemma 1, we can translate $d|(2am+2bn)$ into the inequality

$$d \leq 2(am+bn) \tag{2}$$

Since equation $(2)$ is true for every integer $m$ and $n$, we can allow $m$ and $n$ to represent particular integers by universal instantiation*

In our case, let $m=x$ and $n=y$. Then $am+bn = ax+by$, which allows us to conclude from $(1)$ that $am+bn = 1$.

Therefore, we substitute $am+bn=1$ into $(2)$ to conclude that

$$d \leq 2 \tag{3}$$

which implies that $d=1$ or $d=2$.

  • Universal instantiation is the rule of inference that allows us to conclude that a proposition for a particular element in a domain is true given that that the statement is true for every element in the domain. For example, if the statement, "All women are wise" is true, then the statement "Kaity is wise" is also true.
share|cite|improve this answer

If $\gcd (a,b)=1$, then both $a$ and $b$ can't be even simultaneously. Now two cases arise, Case $1$. Both $a$ and $b$ are odd In this case, both $a+b$ and $a-b$ will be even, so their gcd must be an even number, and so $\gcd (a+b, a-b) = \gcd (2a, a-b) = 2$, as $a-b$ is even. Case $2$. One of the $a$ and $b$ is even and the other is odd In this case, both $a+b$ and $a-b$ will be odd, so their $\gcd$ must be an odd number, and in this case $\gcd (a+b, a-b) = \gcd (2a, a-b) = 1$, as $a-b$ is odd. Note: $\gcd (a, a-b)$ can't exceed $1$ as $a$ and $b$ are relatively prime.

share|cite|improve this answer

As I mentioned in a similar question, this is obvious when viewed in Gaussian integer arithmetic.

Notice $\rm\ n\ |\ a-b,\ a+b\ \Rightarrow\ n\ |\ a-b + (a+b)\ i\ =\ (1+i)\ (a+b\ i)\ $

Hence $\rm\ n\ |\ (1-i)\ (1+i)\ (a+bi)\:,\ $ i.e. $\rm\ n\ |\ 2\ (a+b\ i)\ $ so $\rm\ n\ |\ 2\ $ since $\rm\ (a,b) = 1\:$

Obviously one can generate infinitely many similar exercises by replacing $\rm\ 1+i\ $ by any nonreal Gaussian integer. For example, via $\rm\ (2+ 3\ i)\ (a+b\ i)\ =\ 2\:a-3\:b + (3\:a+2\:b)\ i\ $ we deduce the analogous divisibility result that if $\rm\ gcd(a,b) = 1\ $ then $\rm\ gcd(2\:a-3\:b,\ 3\:a + 2\:b) = 1\:$ or $\:13\:.$

Compare this approach to that in my other answer: here we employ the norm $\rm\ N(2+3\ i) = 13\ $ vs. there we employ the determinant $ = 13\:$ of the linear map $\rm\ x\to (2+3\ i)\ x\:.$

share|cite|improve this answer

This holds true simply because $2$ is the determinant of the linear map $\rm\: (x,y)\to (x-y,\ x+y)\:.\:$ More generally, inverting a linear map by Cramer's Rule (multiplying by the adjugate) yields

$$\rm\begin{pmatrix} a & \rm b \\\\ \rm c & \rm d \end{pmatrix}\ \begin{pmatrix} x \\\\ \rm y \end{pmatrix}\ =\ \begin{pmatrix} X \\\\ \rm Y\end{pmatrix}\ \ \ \Rightarrow\ \ \ \begin{array} \rm\Delta\ x\ \ \ =\ \ \ \rm d\ X - b\ Y \\\\ \rm\Delta\ y\ =\ \rm -c\ X + a\ Y \end{array}\ ,\quad\quad \Delta\ =\ ad-bc $$

Therefore $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y)\:.$

So, in particular, if $\rm\:gcd(x,y) = 1\:$ and $\rm\:\Delta\:$ is prime, we conclude that $\rm\:gcd(X,Y) = 1\:$ or $\rm\:\Delta\:.$

Your problem is simply the special case $\rm\ a = c = d = 1,\ b = -1\ \Rightarrow\ \Delta = ad-bc = 2\:.$

This has a nice arithmetical interpretation in terms of Gaussian integer arithmetic, where the linear map is simply multiplication by $\rm 1 + i\:.\:$ See my other answer here for details.

share|cite|improve this answer

Here's a computational proof, similar to the second proof quanta gave. Since $(x,y) = 1$, there are integers $a,b$ such that $ax+by = 1$. Therefore $$ (a+b)(x+y) + (a-b)(x-y) = 2ax + 2by = 2. $$ Thus $(x+y,x-y)\mid 2$.

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.