2
$\begingroup$

Any ideas on how to prove this equality? I tried various methods, using properties of gcd and lcd, but I can't prove it.

$\endgroup$
  • $\begingroup$ @RSerrao : You could make the same correction in your notation that I made when I edited the question. $\qquad$ $\endgroup$ – Michael Hardy Nov 12 '16 at 1:25
3
$\begingroup$

First we prove that if $\gcd(u,v)=1$ then $\gcd(u+v,uv)=1$

Proof:

If $\gcd(u+v,uv)\neq 1$ there is a prime $p$ such is $p|u+v$ and $p|uv$

Now if $p|uv$ then $p|u$ or $p|v$. Without loss of generality we can assume $p|u$.

Now from $p|u+v$ and $p|u$ we get $p|v$. So $p$ is a common factor of $u$ and $v$. Contradiction.

Going back to the problem:

Assume $d=\gcd(a,b)$ we have $a=du$ and $b=dv$ with $\gcd(u,v)=1$

Also we have $\text{lcm}(a,b)=duv$

So on the right side we have:

$\gcd(d(u+v),duv)=d\gcd(u+v,uv)=d$

Which was to be proved.

$\endgroup$
1
$\begingroup$

Below are a few proofs. We use notation $\ (x,y) := \gcd(x,y)\ $ and $\ [x,y] := {\rm lcm}(x,y)$


First, recalling that gcd distributes over lcm we obtain

$$(a\!+\!b,[a,b])\, =\, [(a\!+\!b,a),(a\!+\!b,b)]\, =\, [(b,a),(a,b)]\, =\, (a,b)$$


Or, cancelling $\,(a,b)\,$ reduces to case $\,(a,b) = 1\,$ so $\,ab = [a,b],\ $ so by Euclid's Lemma

$$\begin{eqnarray}(a\!+\!b,\color{#c00}a) = (b,a)= 1\\ (a\!+\!b,\color{#c00}b)=(a,b)=1\end{eqnarray}\ \Rightarrow\ 1 = (a\!+\!b,\color{#c00}{ab}) = (a\!+\!b,[a,b])$$


Or, by the gcd * lcm law $\,(a,b)[a,b] = \color{#0a0}{ab}\,$ and gcd laws (associative, commutative, distributive)

$$ (a,b)\ (a\!+\!b, [a,b])\ =\ (a(a\!+\!b),\,b(a\!+\!b),\, \color{#0a0}{ab})\ =\ (aa,bb,ab)\ =\ (a,b)^2$$

therefore we infer $\ (a+b,[a,b]) = (a,b)\ $ by cancelling $\ (a,b)\neq 0$

$\endgroup$
0
$\begingroup$

You may want to try and prove first that

$\operatorname{gcd}(a, b) = \operatorname{gcd}(b, a - b)$

This identity should be enough to get you rolling. You will just have to be able to use it correctly.

Alternatively, try this approach. Suppose $d $ is the gcd of $a $ and $b $. Show it divides $a+b $ and $\operatorname {lcm}(a, b) $.

Then suppose $d'$ is the gcd of $a+b $ and $\operatorname {lcm}(a, b) $. Show $d'$ divides both $a $ and $b $. Hence $d $ divides $d'$ which divides $d $, meaning they must be equal.

$\endgroup$
0
$\begingroup$

Let gcd(a,b)=d. a=ds , b=de . a+b=d(e+s). lcm(a,b)=ab/d=des. Assume x greater than d divides des,d(e+s). By the first it divides one of e and s. But if it divides one, it must divide both by the second. But hten dx is the gcd a contradiction.

$\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.