Take the 2-minute tour ×
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|improve this question
add comment

5 Answers

up vote 14 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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.