Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
At the level where this is a relevant exercise, I think abbreviating "$(a\mid c)\land (b\mid c)$" as "$a,b\mid c$" would be Frowned Upon (and similarly $c\mid a,b$ for $(c\mid a)\land (c\mid b)$) -- particularly because the OP seems to have it posed as an exercise in symbolic logic rather than one of number theory. –  Henning Makholm Oct 24 '12 at 18:13
    
@Henning I understand your point, but I think it is essential to choose notation that highlights the innate structure. Writing everything out in first-order logic only serves to obfuscate such. –  Bill Dubuque Oct 24 '12 at 18:22
    
x @Bill: well, yes -- except if (as I strongly suspect is the case here) the point of the exercise is to train the skill of "writing everything out in first-order logic" itself. (Knowing how to do that is useful and enlightening, even though actually doing it is in most practical cases pointless). The OP did tag his question [logic], after all. –  Henning Makholm Oct 24 '12 at 18:27
    
@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. –  Bill Dubuque Oct 24 '12 at 18:31

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

share|improve this answer

If you are lucky, then your proof might be expressed within lattice axiom system:

x ^ y = y ^ x
(x ^ y) ^ z = x ^ (y ^ z)
x ^ (x v y) = x
x v y = y v x
(x v y) v z = x v (y v z)
x v (x ^ y) = x
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.