2
$\begingroup$

If $a,b \in \mathbb{N}$ and $ab > 2$ show that:

$$\text{lcm}(a, b) + \gcd(a, b) \le ab + 1$$

Let the lcm be $l$ and let the gcd be $g$.

We have to show:

$$g + l \le ab + 1$$

I know that:

$$gl = ab > 2$$

WLOG, suppose $a > b$

I have seen that: $g \le b $ and $l \ge b$ But that doesnt help

$\endgroup$
2
  • $\begingroup$ The constraint $ab>2$ is completely unnecesary. This holds for $(a,b)=(1,1)$ and for $\{a,b\}=\{1,2\}$ too. I am assuming $0\not\in\mathbb N$. $\endgroup$ – user26486 Mar 22 '15 at 17:46
  • $\begingroup$ Even if $0\in\mathbb N$ in your context, we would still have a stronger statement if $ab\ge 1$ instead of $ab>2$. $\endgroup$ – user26486 Mar 22 '15 at 19:12
6
$\begingroup$

Since $gl = ab$, we have $$ab + 1 = gl + 1 = g + l + gl - g - l + 1 = g + l +(g - 1)(l - 1) \ge g + l.$$

$\endgroup$
7
  • $\begingroup$ The $ab>2$ constraint is completely unnecessary. The inequality holds without the constraint (assuming OP meant $0\not\in\mathbb N$) and your answer doesn't use it (again, assuming $0\not\in\mathbb N$). $\endgroup$ – user26486 Mar 22 '15 at 17:48
  • 1
    $\begingroup$ Though it is necessary if we assume $0\in\mathbb N$. Peano axioms wikipedia page includes it and Natural number wikipedia page includes it as the common convention. $\endgroup$ – user26486 Mar 22 '15 at 18:03
  • 1
    $\begingroup$ greatest common divisor is not well defined if you allow zero. $\endgroup$ – Joffan Mar 22 '15 at 18:34
  • 1
    $\begingroup$ @Joffan $\gcd(a,b),a,b\in\mathbb N_{0}$ is not well defined iff $a=b=0$. $\gcd(a,0)=a,\forall a\in\mathbb N_{\ge 1}$. So it is defined if you allow at most one zero, just not two (when talking about $\gcd$ of two numbers). $\endgroup$ – user26486 Mar 22 '15 at 19:10
  • 1
    $\begingroup$ Instead of assumptions, it would probably be better if the OP would be edited to use $\mathbb{N}^+$ or $\mathbb{N}^0$. $\endgroup$ – nyuszika7h Mar 22 '15 at 22:11

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.