I made a proof by contradiction.

Suppose $δ=(a+b,\operatorname{lcm}[a,b])$ and let it be that $δ\neq(a,b)$.

Then $\exists ε\big(ε=(a,b) \land ε\gt δ \big) \implies ε|a \land ε|b \implies ε|(a+b)$.

It is also true that $ε|\operatorname{lcm}[a,b]$.

By the two previous statements, we get that $ε|(a+b,\operatorname{lcm}[a,b])\implies ε|δ$. This is absurd since $ε>δ$.

Thus $δ=(a,b)$.

Is it correct? I wonder if i made errors during my logical analysis. Thanks in advance.

  • 2
    $\begingroup$ What does $[a,b]$ mean in this context? $\endgroup$ – Aaron Jul 10 '16 at 0:00
  • $\begingroup$ It's the least common multiple (lcm). How should i denote it in Latex? $\endgroup$ – Nikos Jul 10 '16 at 0:01
  • 1
    $\begingroup$ You could do \operatorname{lcm}(a,b). $\endgroup$ – Aaron Jul 10 '16 at 0:03
  • $\begingroup$ First, note that this isn't really a proof by contradiction: you didn't use the assumption $\epsilon>\delta$ anywhere, but rather you directly proved that $\epsilon\mid\delta$ and thus $\epsilon\le\delta$. (Perhaps you should justify why $\epsilon\mid[a,b]$.) Taking out the proof-by-contradiction wrapper will make it clearer. Second, you've managed to prove that $\epsilon\le\delta$, but you also need to prove $\epsilon\ge\delta$—perhaps by showing that $\delta$ divides both $a$ and $b$. $\endgroup$ – Greg Martin Jul 10 '16 at 0:18

Below are a few of many possible proofs.

Using the fact the gcd distributes over lcm we obtain

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

Cancelling $\,(a,b)\,$ we reduce to the 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])$$

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

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


Let $m=\gcd (a,b).$

We have $a=xm$ and $b=ym$ where $\gcd (x,y)=1.$ Then lcm $ (a,b)=mxy.$ Proof: $\;mxy$ is a common multiple of $a, b.$ If $a|c$ then $c=az=mxz.$ And if also $b|c,$ we have $ym|mxz. $... So $y|xz,$ so $y|z$ ...(because $\gcd (y,x)=1)$...Hence $z=yz',$ implying $c=az=mxz=mxyz'.$

Therefore $$\gcd (a+b, \text {lcm} (a,b))=\gcd (xm+ym, xym)=m\cdot \gcd (x+y, xy).$$ Now if $p$ is prime and $p$ divides both $x+y$ and $xy$ then either $(p|x\land p|(x+y)$ or $(p|y\land p|(x+y).$ But either of these implies $(p|x\land p|y)$, which cannot be, as $p>1=\gcd (x,y).$ Therefore $\gcd (x+y,xy)=1$ and we are done.


How do you know that $\epsilon>\delta$? If I were to prove this, I would start by assuming without loss of generality that $\gcd(a,b)=1$. Then, find a contradiction when a prime $p$ divides both $a+b$ and $ab$.

  • $\begingroup$ Since $ε=\gcd(a,b)$, then $ε|a \land ε|b$. It follows $ε|(a+b) \land ε|\operatorname{lcm}[a,b]$. So it must be that $ε>δ$. Right? $\endgroup$ – Nikos Jul 10 '16 at 0:11
  • $\begingroup$ Doesn't that imply $\epsilon \leq \delta$? $\endgroup$ – Batominovski Jul 10 '16 at 0:14

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.