0
$\begingroup$

How to prove that $gcd(a+b,a-b) \ge gcd(a,b)$?
I am confused, is this related to Bezout's theorem?

$\endgroup$
2
  • 1
    $\begingroup$ Just asking shouldn't it be: $gcd(a+b, a-b) \ge gcd(a,b)$? Tried using $a=24$, $b=2$. $\endgroup$
    – Mayank M.
    Mar 25 '17 at 9:39
  • $\begingroup$ Yes, thanx, if u want u can edit $\endgroup$
    – ami_ba
    Mar 25 '17 at 9:43
2
$\begingroup$

If $d$ divides $a+b,a-b$ both

$d$ must divide $a+b+(a-b)=2a$ and $a+b-(a-b)=2b$

$\implies d$ must divide $(2a,2b)=2(a,b)$

Conversely, if $n=(a,b); n$ must divide $a\pm b\implies n$ must divide $(a+b,a-b)$

$\endgroup$
5
  • $\begingroup$ There should be a correction in the second line your of answer sir. $\endgroup$
    – Mayank M.
    Mar 25 '17 at 9:43
  • $\begingroup$ @MayankM., Thanks $\endgroup$ Mar 25 '17 at 9:44
  • $\begingroup$ I did not get it. $\endgroup$
    – ami_ba
    Mar 25 '17 at 9:47
  • 1
    $\begingroup$ @AmitayasBanerjee, Trying checking for (odd, odd);(odd, even);(even, even) values of $a,b$ $\endgroup$ Mar 25 '17 at 9:51
  • $\begingroup$ Thanx, I got it $\endgroup$
    – ami_ba
    Mar 25 '17 at 9:58
1
$\begingroup$

Although the question has been solved I just wanted to try this approach. I'd like to read some comment about it.
Let $$a=a_1^{\alpha_1} \cdot\space\dots\space\cdot a_n^{\alpha_n}$$
$$b = b_1^{\beta_1} \cdot\space\dots\space\cdot b_m^{\beta_m}$$

Now, let $HCF (a,b) = \lambda$.
$\implies a-b = \lambda [(a_i^{x_1} \cdot\space\dots\space\cdot a_{i+k}^{x_k}) - (b_j^{y_1} \cdot\space\dots\space\cdot b_{j+k}^{y_k})]$
$\implies a+b = \lambda [(a_i^{x_1} \cdot\space\dots\space\cdot a_{i+k}^{x_k}) + (b_j^{y_1} \cdot\space\dots\space\cdot b_{j+k}^{y_k})]$

Let, $p=[(a_i^{x_1} \cdot\space\dots\space\cdot a_{i+k}^{x_k}) - (b_j^{y_1} \cdot\space\dots\space\cdot b_{j+k}^{y_k})]$,
$q=[(a_i^{x_1} \cdot\space\dots\space\cdot a_{i+k}^{x_k}) + (b_j^{y_1} \cdot\space\dots\space\cdot b_{j+k}^{y_k})]$.
$\implies HCF(a+b, a-b) = \lambda \cdot HCF(p,q) = HCF(a,b)\cdot HCF(p,q)$

Therefore, $HCF(a+b, a-b) \ge HCF(a,b)$.

$\endgroup$
1
  • $\begingroup$ This is really what I was looking for! $\endgroup$
    – ami_ba
    Mar 26 '17 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.