6
$\begingroup$

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

  • 3
    +1 for showing some thought and trying something before posting.2011-02-01

3 Answers 3

10

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 , so $\mathrm{gcd}(a+b,a-b)$ divides .

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

So $\mathrm{gcd}(a+b,a-b)$ divides $\mathrm{gcd}($,$) = $.

(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).

  • 0
    @Arturo Magidin: Haha, I got it. Much simpler than I thought. Thanks a lot!2011-02-01
  • 0
    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?2011-02-01
  • 0
    @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).2011-02-01
  • 0
    @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.2011-02-01
  • 0
    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$.2011-02-01
  • 0
    Thanks again for the confirm.2011-02-01
  • 0
    [See here](http://math.stackexchange.com/questions/32737/prove-gcdab-a-b-1-or-gcdab-a-b-2-if-gcda-b-1/32894#32894) for a generalization using determinants and [here](http://math.stackexchange.com/questions/32737/prove-gcdab-a-b-1-or-gcdab-a-b-2-if-gcda-b-1/33104#33104) using norms.2011-06-13
  • 0
    what does that mean , ??2016-10-13
2

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

  • 0
    Thanks for a great hint ;)2011-02-01
2

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.

  • 0
    [See here](http://math.stackexchange.com/questions/32737/prove-gcdab-a-b-1-or-gcdab-a-b-2-if-gcda-b-1/33104#33104) for a generalization using norms.2011-06-13