1
$\begingroup$

There is a nice (duality) characterization of the greatest common divisor (wiki) of two integers $a$ and $b$ known as the Bézout's identity: $gcd(a,b)$ is the smallest positive integer that can be written as $ax + by$.

Is there a similar characterization of the least common multiple of two integers $a$ and $b$ such as "$lcm(a,b)$ is the largest $\ldots$"?

$\endgroup$
2
$\begingroup$

You can use Bézout's identity and the following relationship between the greatest common divisor and the least common multiple to come up with a characterization of $lcm(a,b)$. $$gcd(a,b) \times lcm(a,b) = a\times b \quad... \;\;(1)$$ $$lcm(a,b) = \frac{ab}{ax+by}$$

However, I am not aware of any other characterizations.


EDIT:

Added proof of (1)

$\endgroup$
  • 1
    $\begingroup$ So lcm(a,b) is the largest integer of the form ab/(ax+by) for any integers x,y. $\endgroup$ – DanielWainfleet Mar 27 '17 at 6:50
1
$\begingroup$

Actually the definition of $\gcd(a,b)$, valid in any P.I.D., is that it is a generator of the ideal $(a,b)$. In $\mathbf Z$, there are two generators, but is a canonicaay to choose one: it is to take the positive generator. In $F[X]$ ($F$ a field), we usually choose the monic generator.

In other P.I.D.s, there is usually no canonical way, as the g.c.d. is defined within a unit factor. For instance, in ring of Gaussian integers $\mathbf Z[i]$, the units are $\;\{1,-1,i,-i\}$ and there is no specific reason to choose one particular g.c.d.

The dual characterization of the l.c.m. of $a$ and $b$ is that it is a generator of the ideal $\;(a)\cap (b)$. In $\mathbf Z$, we likewise choose the positive generator.

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