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.

Problem:

Prove that if gcd( a, b ) = 1, then gcd( a - b, a + b ) is either 1 or 2.

From Bezout's Theorem, I see that am + bn = 1, and a, b are relative primes. However, I could not find a way to link this idea to a - b and a + b. I realized that in order to have gcd( a, b ) = 1, they must not be both even. I played around with some examples (13, 17), ...and I saw it's actually true :( ! Any idea?

Thanks,
Chan

share|improve this question
3  
+1 for showing some thought and trying something before posting. –  Ross Millikan Feb 1 '11 at 4:32

3 Answers 3

up vote 10 down vote accepted

The gcd of $x$ and $y$ divides any linear combination of $x$ and $y$. And any number that divides $r$ and $s$ divides the gcd of $r$ and $s$.

If you add $a+b$ and $a-b$, you get <blank>, so $\mathrm{gcd}(a+b,a-b)$ divides <blank>.

If you subtract $a-b$ from $a+b$, you get <blankity>, so $\mathrm{gcd}(a+b,a-b)$ divides <blankity>.

So $\mathrm{gcd}(a+b,a-b)$ divides $\mathrm{gcd}($<blank>,<blankity>$) = $<blankety-blank>.

(For good measure, assuming the result is true you'll want to come up with examples where you get $1$ and examples where you get $2$, just to convince yourself that the statement you are trying to prove is the best you can do).

share|improve this answer
    
@Arturo Magidin: Haha, I got it. Much simpler than I thought. Thanks a lot! –  Chan Feb 1 '11 at 4:33
    
By the way, I can't go from gcd( a + b, a - b ) right? since this is inverse error if A then B, does not guarantee B then A. Should I prove it by contradiction instead? –  Chan Feb 1 '11 at 4:36
    
@Chan: I'm not sure what you mean... You cannot begin by assuming that gcd(a+b,a-b) is equal to 1 or to 2, but you do not need to make any assumption. The hints above give you information about what gcd(a+b,a-b) must divide, and you have other information (remember what you are told about $a$ and $b$). All of that together should be sufficient (PEV was more explicit, and you seemed to think it was a great hint). –  Arturo Magidin Feb 1 '11 at 4:46
    
@Arturo Magidin: All I tried to say is that, when proving if A then B. If we assume B is true, then infer A is true -> this is wrong. –  Chan Feb 1 '11 at 4:46
    
Yes. You should never affirm the consequent. If you assume B is true and infer A is true, then you prove $B\rightarrow A$, which may be something interesting, but is not equivalent to $A\rightarrow B$. –  Arturo Magidin Feb 1 '11 at 4:47

Note that $d|(a-b)$ and $d|(a+b)$ where $d = \gcd(a-b, a+b)$. So $d$ divides the sum and difference (i.e. $2a$ and $2b$).

share|improve this answer
    
Thanks for a great hint ;) –  Chan Feb 1 '11 at 4:34

HINT $\rm\quad a-b\ +\ (a+b)\ i\ =\ (1+i)\ (a+b\ i)\ \ $ provides a slick proof using Gaussian integers. This reveals the arithmetical essence of the matter and, hence, suggests obvious generalizations.

share|improve this answer
    
See here for a generalization using norms. –  Bill Dubuque Jun 13 '11 at 16:48

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.