# Prove that $\gcd( a + a', b + b' ) = 1$ if $ab - a'b' = \pm 1$

Prove that $gcd(a + a', b + b') = 1$ if $ab - a'b' = \pm 1$

My attempt was:
Case 1:
$ab - a'b' = 1 \implies \gcd(a, b') = 1$ and $\gcd(a', b) = 1$

Then is it sufficient to conclude that $\gcd(a + a', b + b') = 1$?

Furthermore, when we write $\pm 1$, does it mean or or and?

Thanks,

-
How could it possibly mean "and"? – Qiaochu Yuan Mar 1 '11 at 1:01

No, $\text{gcd}(a,b) = 1$ and $\text{gcd}(x,y) = 1$ does not imply $\text{gcd}(a+x, b+y) = 1$.

For instance, $\text{gcd}(a,b) = \text{gcd}(b,a) = 1$ does not mean $\text{gcd}(a+b, a+b) = 1$.

The $\pm 1$ means OR.

Hint: to the question in title:

Can you find $x$ and $y$ so that $(a+a')x - (b+b')y = ab - a'b'$?

-
 Thank you, I understand it now. Your counter example is very nice ;). By the way, could you give me a hint? – Chan Mar 1 '11 at 1:10 @Chan: I have edited the answer to give a hint. – Aryabhata Mar 1 '11 at 1:22 +1. This was what I had in mind as well. – user17762 Mar 1 '11 at 4:55 Now I got it ;) ! Thank you. I was trying the reverse :(. – Chan Mar 1 '11 at 5:00

Here's one way of looking at these problems. In general, integers $m$ and $n$ are relatively prime if and only if there are integers $x$ and $y$ such that $mx - ny = \pm 1$. You can write this in matrix form as $$det\pmatrix {m&n \cr y&x \cr} = \pm 1$$ Correspondingly, the condition you are given is that $$det\pmatrix {a&b' \cr a'&b \cr} = \pm 1$$ Adding one row to another doesn't change the determinant, so you also have $$det\pmatrix {a + a'&b + b' \cr a'&b \cr} = \pm 1$$ This gives that $a + a'$ and $b + b'$ are relatively prime.

-
+1: Very nice..! – Aryabhata Mar 1 '11 at 3:40
+1: Nice way to look at it. A minor typo though. The first entry of the determinant should read $a+a'$ – user17762 Mar 1 '11 at 4:51
thanks, both of you, corrected it. – Zarrax Mar 1 '11 at 5:06