5
$\begingroup$

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,

  • 0
    See also: [If $ab - a'b' = \pm 1$, then $(a + a', b + b') = 1$](https://math.stackexchange.com/q/2566355)2017-12-15

2 Answers 2

6

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'?

  • 0
    Now I got it ;) ! Thank you. I was trying the reverse :(.2011-03-01
10

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.

  • 0
    thanks, both of you, corrected it.2011-03-01