2
$\begingroup$

I am trying to write a proof for the least common multiple lcm(x, y), where lcm(x,y), x, and y are of course integers. What are the properties of lcm(x,y) written symbolically in mathematical logic notation.

2 Answers 2

2

Below are dual universal definitions of $\rm\,lcm\,$ and $\rm\,gcd\,$ that work in $\,\Bbb Z\,$ (or any integral domain).

Definition of LCM $\quad$ If $\quad\rm a,b\:|\:c \;\iff\; [a,b]\:|\:c \quad\;$ then $\quad\rm [a,b] \;$ is an LCM of $\:\rm a,b$

Definition of GCD $\quad$ If $\quad\rm c\:|\:a,b \;\iff\; c\:|\:(a,b) \quad$ then $\quad\rm (a,b) \;$ is an GCD of $\:\rm a,b$

Note that $\;\rm a,b\:|\:[a,b] \;$ follows by putting $\;\rm c = [a,b] \;$ in the definition. Dually $\;\rm (a,b)|\:a,b \:.$

These definitions are equivalent to the more specific notions employed in Euclidean domains.

If you know a little category theory then you may recognize the definitions as special cases of (co)products. See this question for further discussion. See also this question for viewpoints from adoints and Yoneda's Lemma, and see here for an analogy: the $\rm\,floor\,$ funciton as a right adjoint. Compare the proof there to the proof below.

Such universal $\iff$ definitions frequently enable one to give slick proofs that concisely unify both arrow directions, e.g. consider the following proof of the fundamental $\rm\,lcm * gcd\,$ identity.

Theorem $\rm\;\; (a,b)\, =\, ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.

Proof $\rm\quad\ d\:|\:a,b \iff a,b\:|\:ab/d \iff [a,b]\:|\:ab/d \iff d\:|\:ab/[a,b] \quad$ QED

  • 0
    @Henning It certainly would help if the OP provided more context. It could be number theory used as an example for a logic exercise, or it could be a true question in number theory, whose goal is to understand the foundations (or logic) of lcm and gcd.2012-10-24
0

For positive integers $x, y$, the least common multiple $\operatorname{lcm}(x,y)$ may be uniquely described by the following (using $\mid$ for the "divides" relation (in fact, ordering) ):

$\forall z: x \mid z \land y \mid z \implies \operatorname{lcm}(x,y) \mid z$

If you are familiar with this language, this observataion can be expressed by saying that $\operatorname{lcm}(x,y)$ is the least upper bound, or supremum of $x$ and $y$ in the poset $(\Bbb N, \mid)$. Similarly, $\operatorname{gcd}(x,y)$ is the infimum of $x$ and $y$.