3
$\begingroup$

I started by saying that $\gcd(a,b) = d_1$ and $\gcd(a+b,\gcd(a,b)) = d_2$

Then I tried to show that $\ d_1 \ge d_2, d_1 \le d_2$.

I know that $\ d_2 | \gcd(a+b, d_1)$ hence $\ d_2 \le d_1 $.

How do I prove that $\ d_2 \ge d_1$ ?

$\endgroup$
10
  • 4
    $\begingroup$ What is $\gcd(a+b)$? $\endgroup$ – Angina Seng Nov 26 '17 at 18:41
  • $\begingroup$ @LordSharktheUnknown What do you mean by what is $\gcd(a+b)$ ? $\endgroup$ – Dannz Nov 26 '17 at 18:43
  • 1
    $\begingroup$ What Lord means is, how can you have a gcd of one single number, here being $a+b$? $\endgroup$ – imranfat Nov 26 '17 at 18:44
  • $\begingroup$ Do you mean $\gcd(a+b, \gcd(a,b))$? $\endgroup$ – Zubin Mukerjee Nov 26 '17 at 18:44
  • $\begingroup$ @imranfat My apologies its a typo. $\endgroup$ – Dannz Nov 26 '17 at 18:45
4
$\begingroup$

If $\gcd(a,b)=d_1$ then $a = d_1 x$ and $b= d_1 y$, where $x,y$ are integers. Consequently, $$\gcd(a+b,\gcd(a,b))=\gcd(d_1(x+y),d_1) = d_1\gcd(x+y,1)=d_1.$$

$\endgroup$
1
$\begingroup$

$d_1$ divides $a$ and $b$, thus it divides $a+b$, and it divides $\gcd (a,b) $ (i.e. itself), thus $d_1$ divides $d_2$.

$\endgroup$
1
$\begingroup$

We have that $\exists x,y \in \mathbb{Z}$ s.t. $(a+b)x + d_1y = d_2$ by Euclid's Algorithm. Note that $d_1$ divides the LHS, so we must have $d_1 \mid d_2$ and hence the proof.

$\endgroup$
1
$\begingroup$

Don't worry about size so much as what they divide.

1) $\gcd(a,b)=d_1$ by definition divides $a$ and $b$ and thus $a+b$. And everything divides itself. So $\gcd(a,b)$ is a common divisor of $a+b$ and $\gcd(a,b)$ (and thus by definition is less or equal to the greatest common divisor of $a+b$ and $\gcd(a,b)$. $d_1 \le d_2$).

2) Likewise $\gcd(a+b, \gcd(a,b))= d_2$ divides $\gcd(a,b)$. So $d_2$ divides everything that $\gcd(a,b)$ divides so $d_2|a$ and $d_2|b$. So $d_2$ is a common divisor of $a$ and $b$ (and thus by definition is less than or equal to the greatest common divisor of $a$ and $b$. $d_2 \le d_1$.)

Obligatory fleablood essay: It's best not the think of the "greatest" in greatest common divisor as size as in "Five is bigger than four" but more in the sense of "completeness". The size of the GCD is of little interest or importance. What really matters is that can't find a more "comprehensive" factor but adding an additional component factor to GCD or by replacing a component factor of the GCD with another.

As a direct consequence the GCD is the largest possible factor but that is mostly and usually irrelevant.

Many text do not define the "greatest common factor" as "the common factor that is greatest" but as "the common factor so that all other common factors will divide into it". I, personally, find this a troubling definition because i) it sounds much more obscure and obtuse than it actually is and ii) we must prove that there is such a number and that it is unique.

But I do like that it relates directly wot what does and does not divide the two terms and how.

By that definition: 1) above says $d_1|d_2$ and 2) says $d_2|d_1$ so (assuming we are dealing with positive integers) $d_1 = d_2$.

$\endgroup$

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.