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
    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 h$i$nt ;)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